title: Terminology for trees

text:
# Question
Title: Terminology for trees
In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, in a binary tree, I would like to refer to the right sibling of the node, the right child of this one, etc..

Can I call these the first four rightmost immediate descendants of a node? Is the term "immediate" really clear?

Thank you very much.

# Answer
> 3 votes
No, the phrase "the first four immediate descendants" doesn't say what you want. In particular, "first four" sounds like you're talking about four vertices, not four *levels* of vertices. If I read "immediate descendants" I'd be confused because it sounds like it should mean the same as "children" but surely you'd just say "children" if that's what you meant.

I would describe the vertices you want as being the set of all descendants of some node $v$ that are within distance $4$ of $v$. If you need to say it often and the number four is fixed, you could explicitly define a term such as "close descendants" to mean this.

Long story short, there's no standard term for the concept you want to describe so you must describe it explicitly and define any name you want to use for it.

# Answer
> 2 votes
There is no such name. The best way to describe what you want is, well, to specify it using language or mathematics. Don't expect an existing name for every concept you ever dream up; this is why we have language, so we can express novel concepts.

Personally, I don't find "the first four immediate descendants of a node" clear at all, so I'd suggest you define it more precisely. For instance, it's not clear what ordering you have in mind on the descendants, so "first four" doesn't seem well-defined.

# Answer
> 1 votes
As others have stated there is no term for "first four" immediate descendants. However, if you have $n$ as a parent node, $n$ could have 4 *children* or 4 *successors* that branch from it.

---
Tags: graphs, data-structures, terminology, trees
---


# Question
Title: How to use an algorithm to find a satisfying assignment in polynomial time?
I am currently trying to solve the following problem but I am unsure how to go about it. The problem states:

Suppose that someone gives you a polynomial-time algorithm to decide 3-SAT. Describe how to use this algorithm to find a satisfying assignment in polynomial time.

To my understanding the 3-SAT is simply a conjunction of any 3 disjunctions that turns out to be true (i.e. something like (x1 | x2 | x3) & (x4 | x5| x6) where **| represent or** and **& represents and**). In this case you could have used any ordering of the variables and you could have negated them at your pleasure. Furthermore You can keep adding conjunctions, but each one has to have 3 variables. Please correct me if I am wrong in any statement above.

Now, they want us to find a satisfying assignment in polynomial time, meaning values of x1, x2, x3, x4, x5, x6 that make the value true. However, isn't that what we are given in the first place? I am confused as to what to do and if I am interpreting the question correctly.

# Answer
The algorithm that decides 3-SAT just answers yes or no, satisfiable or not. It doesn't (directly) give you an assignment for the variables. You have to use the decision algorithm as a black box to find an assignment of the variables. You should try adding a something to your formula that lets you deduce the assignment of a particular variable without changing the satisfiability.
> 6 votes

---
Tags: satisfiability, np, 3-sat
---


# Question
Title: If $A$ is m-complete for $\Sigma_n$, is $\overline{A}$ m-complete for $\Pi_n$?
If we have a set $A$ that is m-complete for $\Sigma\_n$, then is it's complement $\overline{A}$ m-complete for $\Pi\_n$?

I know that $\overline{A} \in \Pi\_n$, but does it inherit the completeness?

I think this makes sense but I can't seem to think of any formal reasons why.

# Answer
> 0 votes
Hint: use the fact that $A\le\_p B \iff \overline{A} \le\_p \overline{B}$ (the same reduction works for both sides).

Try proving this for $NP,coNP$ first, and then check if your proof generalizes to the n'th level too.

---
Tags: computability
---


# Question
Title: How does RAID-5 algorithm locate the right device?
Please consider the following diagram of a RAID-5 array (Ignore the gray background):

Now, given a logical address, how can one return the device number (0-3)?

For example, DeviceByLogicalSector(50) = 0, DeviceByLogicalSector(31)=2.

I've need to implement DeviceByLogicalSector method. I can use space if that's required.

Now, I've noticed the following:
Let's observe only the first $4$ rows; If we have a sector which is above the $P$-diagonal then the formula is: $\frac{(\text{logical\_addr} \mod 12)}{4}$. And if the sector is below the diagonal then we need to add $1$.

Thanks

# Answer
> -1 votes
Extracted from: HERE

```
// Assume all indexes are zero-based.
// Algorithm = Left-Asym

ChunkIndex = LogicalSector / SectorsPerChunk
StripeIndex = ChunkIndex / (DiskCount - 1)

ParityDisk = (DiskCount - 1) - ((StripeIndex / ParityDelay) % DiskCount)

DataDisk = (LogicalSector % (SectorsPerChunk * (DiskCount - 1))) / SectorsPerChunk
If ParityDisk <= DataDisk:
    DataDisk = DataDisk + 1

PhysicalSector = (LogicalSector / SectorsPerChunk) * (DiskCount - 1)
PhysicalSector = PhysicalSector * SectorsPerChunk
PhysicalSector = PhysicalSector + (LogicalSector % SectorsPerChunk)

```

---
Tags: computer-architecture, operating-systems, number-theory, matrices, memory-hardware
---


# Question
Title: Recommendations for a good (rigorous) text to study Computational Complexity.
I look for a good text to learn basics of computational complexity.

I've read some parts of the first two chapters of "*Computational Complexity: A Modern Approach*" by Boaz Barak and Sanjeev Arora, it's readable and gives the big picture but I find it not to be rigorious enough for me. I'm a mathematics student so I want a more rigorous treatment of the subject. So, the text I look for should:-

1- Define Turing machines formally and prove the basic results in a formal way not using handy-waving arguments. For example, Boaz treatment of Turing machines is not rigorous and so I'd love to see more precise treatment of that.

2- Give proofs that are rigorous enough like those I read in mathematics texts and are not just "overviews".

What are your recommendations? What is the texts that satisfies my needs as close as possible?

# Answer
> 3 votes
Following are my recommendations:

1. Introduction to Theory of Computation by Michael Sipser. It is an introductory book. Although proofs are complete and not hand waving, but not much maths is needed as a pre requisite. Although Turing machines are covered nicely.
2. Complexity and cryptography by Talbolt and Welsh. In this book little math background is required. Turing machines is not covered in much details. But the book gives proofs for almost all theorem's it introduces.
From my experience ( as I am a beginner myself ) Sanjeev Arora and Boaz Barak is the most concise with covering advanced topics like quantum computation etc. Although I think you should have a back ground in probability, number theory to read the part I of the book intended to be for undergraduates, as the book leaves some proofs upto the readers. Again for number theory the book I find readable as ( as there is no pre requisite ) : Number theory by Willian Stein.

# Answer
> 2 votes
The topics you have mentioned mostly belong to Theory of Automata. I think the book *Introduction to Automata Theory, Languages, and Computation* (2nd edition) by Hopcroft and Ullman is what you want.

The book by Arora and Boaz, thought not mentioned, does assume you are well conversed with theory of automata. They however need more rigorous time and space bounds for Turing machines in their book, for which they have given quite extensive proofs.

So Arora and Boaz is a good book for Computational Complexity but not a great book if you are interested only in Theory of Automata or NP completeness (both are dealt with and finished in one or two chapters, till chapter 4, if I remember correctly).

Honestly, I am surprised that you think that Arora and Boaz's book is not rigorous. Their style, as I understand, is to give proofs for difficult theorems, but leave proofs for simpler theorems by giving sufficient hints and/or by giving proofs for specific cases. This saves the book from having excessive symbols, subscripts, and superscripts bloat that many other text books and almost all scientific papers suffer.

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


# Question
Title: How to prove that $n$ sets have maximum of $2^n-1$ disjoint subsets when you have operations $\cup , \cap , \setminus$?
I just found out that you can have $2^{2^n-1}$ different subsets, made from $n$ sets, using operations $\cup , \cap , \setminus$.

That is because when $n=2$, for example, you have 3 disjoint subsets: $A\setminus B, B\setminus A,A\cap B$ and then you can union those things together in $2^3-1$ different ways (plus the empty set) to get $8$ different unequal sets.

My question is, how to prove that the number of those disjoint subsets is $2^n-1$.

Pictorial definition of what disjoint subsets are:

In the picture above I have enumerated disjoint subsets of $2$ and $3$ sets. As you can see their number is $2^n-1$.

# Answer
Proof by induction.

Suppose for $n=2$ it's true. (Obvious from Venn diagram with 2 sets).

Let's prove for $n=k+1$:

Suppose we have k sets, then we have $2^k-1$ disjoint subsets. Now we add another set. Then that set is supposed to be in intersection with $2^k-1$ of previous subsets and have a part that doesn't intersect with anything, hence we get $2\*(2^k-1)+1=2^{k+1}-1$ subsets.

From picture above you can see how C is added to A and B.
> 0 votes

# Answer
First of all, your question is not really well-defined, or put differently, the claim is incorrect in general. Consider for example $A = B = \emptyset$, in which there is only one set which you can get, namely $\emptyset$.

There are at least two ways in which we can address this problem. The first is to assume that the starting sets are "generic", that is, they don't enjoy any "special" properties. This is a vague description, but it can be formalized by saying that in the "Venn diagram" of the sets (which I describe below), all regions are non-empty.

The second way is to do everything formally. We think of $A$ or $A \setminus B$ not as a set but as a formal expression defined in an appropriate language. We then make two expressions equal if they are equal whenever you substitute actual sets. For example, $A = A \cap A$ and $A \setminus (A \setminus B) = A \cap B$. You can also define equality syntactically if you prefer.

Another problem with your claim is that it's not clear what you mean by "the sets have $2^n-1$ non-overlapping subsets". For example, $A \cap B$ and $A \setminus B$ are non-overlapping, and this is a maximal collection of non-overlapping subsets (in general). You mean something else, and again there are several possible interpretations. This time all interpretations I can think of only serve to complicate things and make them less intuitive, so I'll just explain what is meant by the claim, and you think of an appropriate interpretation.

The *Venn diagram* of the sets $A\_1,\ldots,A\_n$ consists of the $2^n$ regions which you can get by intersecting either $A\_i$ or $\overline{A\_i}$ *for each $i$*. That is, for each $i = 1,\ldots,n$ we choose $A\_i$ or $\overline{A\_i}$, and then compute the intersection of these $n$ sets. You can web-search "Venn diagram" to see pictorial representations.

You can prove by induction (exercise) that any set that you can obtain from (possibly multiple copies of) $A\_1,\ldots,A\_n$ using $\setminus$, $\cup$ and $\cap$ is a union of regions of the Venn diagram; indeed, a union which doesn't include the region $\overline{A\_1} \cap \cdots \cap \overline{A\_n}$. Moreover, you can easily get any of these $2^n-1$ regions individually (exercise), and these are your "$2^n-1$ non-overlapping subsets". In total, you can get any union of these $2^n-1$ regions (exercise), and so you can "reach" $2^{2^n-1}$ different expressions.

One possible formulation of your two claims are as follows. First, the maximal number of disjoint sets that can be formed from $A\_1,\ldots,A\_n$ is $2^n-1$ (under the caveats described in the second paragraph); this can be proved using the exercises mentioned above. Second, the number of different sets that can be formed (again, under the same caveats) is $2^{2^n-1}$, which again follows from these exercises.
> 3 votes

---
Tags: sets
---


# Question
Title: Complexity of finding factors of a number
I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division:

1. For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ then add $d$ and $n/d$ to the factor list. Assuming division and appending to a list are $O(1)$ operations for a CPU, this seems to be $O(\sqrt n)$.

The second is to use trial division with prime factors:

1. Sieve all primes up to $\sqrt n$. The time complexity of the Sieve of Eratosthenes is $O(n \log \log n)$, so this is $O(\sqrt n \log \log \sqrt n)$?
2. From that list of primes, repeatedly try to divide by $p$ and move on to the next prime if the current prime will not divide evenly anymore. If it does divide, add $p$ and $n/p$ to the factor list. The density of primes is $n / \ln n$, and since primes go up to $\sqrt n$ the supposed time complexity is $O(\sqrt n / \ln \sqrt n)$. However, this does not take into account dividing by primes more than once.

I would like to know if my analysis is correct. It seems counter-intuitive that trial division only takes $O(\sqrt n)$ time, but $n$ is integer size, not input length. I don't think the time complexity of the second method is correct, but I am sure it must be faster than the first (trying primes instead of all numbers within a range).

# Answer
When you assume that arithmetic operations can be done in time $O(1)$, you're assuming that the numbers you're dealing with have a constant maximum number of digits. That's not a reasonable assumption when you're dealing with factorization: for any number $d$ of digits, there are a fixed, finite number of integers with at most $d$-digits and you can compute their factorizations in constant time.

In reality, the cost of performing arithmetic operations on numbers depends on the size of those numbers. A $b$-bit number can be anything between $0$ and $2^b$ (strictly, $2^b-1$ but that makes no real difference). As such, you're proposing to do $\sqrt{2^b} = 2^{b/2}$ trial divisions to determine the factors of a $b$-bit number. That's not polynomial in the input length; rather, it's polynomial in the magnitude of the numbers represented in the input. So what you have is a "pseudopolynomial-time algorithm". (Another way of looking at this is that your algorithm would run in polynomial time if you represented numbers in unary instead of in binary).
> 6 votes

# Answer
The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (where $n$ is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model only allows you to perform an operation involving a constant number of bits; and the second model allows you to perform a constant number of arithmetic operations (addition, subtraction, multiplication, division) on registers of length $C\log n$, where $C$ is some constant which you can use but must depend only on the algorithm.

In both models, the division operation itself won't take $O(1)$; indeed, the CPU cannot divide a large number $N$ by a prime $p$ in $O(1)$. So the running time is really $O(\sqrt{N}(\log N)^{O(1)})$ (where $N$ is the number you're trying to factor). We usually don't care about these logarithmic factors, so we use the notation $\tilde{O}(\sqrt{N})$, and we explain that it hides logarithmic factors.
> 5 votes

# Answer
> this does not take into account dividing by primes more than once.

But that is exactly why the problem of integer factorization is hard. It can not be decided efficiently (I.e. in polynomial time) how many times each prime occurs in the factorization. Both your analysis' assume each prime occurs either once or not.

In other words. The hardness doesn't lie in the fact of finding out which primes are part of the factorization (i.e. at least once or not) , but how many times each prime occurs (not, once, twice, ...?).

In even other words. You can, using your algorithms, decide which primes will be part of the factorization but now how many times they will occur.

The wikipedia article on this problem is pretty extensive
> -3 votes

---
Tags: complexity-theory, time-complexity, factoring, primes
---


# Question
Title: Why does garbage collection extend only to memory and not other resource types?
It seems like people got tired of manual memory management, so they invented garbage collection, and life was reasonably good. But what about every other resource types? File descriptors, sockets, or even user created data like database connections?

This feels like a naive question but I cannot find any place where anyone has asked it. Let's consider file descriptors. Say a program knows that it will only be allowed to have 4000 fds available when it starts. Whenever it performs an operation that will open a file descriptor, what if it would

1. Check to make sure that it isn't about to run out.
2. If it is, trigger the garbage collector, which will free a bunch of memory.
3. If some of the memory freed held references to file descriptors, close them immediately. It knows the memory belonged to a resource because the memory tied to that resource was registered into a 'file descriptor registry', for lack of a better term, when it was first opened.
4. Open a new file descriptor, copy it into new memory, register that memory location into the 'file descriptor registry' and return it to the user.

So the resource would not be freed promptly, but it would be freed whenever the gc ran which includes at the very least, right before the resource was about to run out, assuming it isn't being entirely utilized.

And it seems like that would be sufficient for many user defined resource cleanup issues. I managed to find a single comment here that references doing cleanup similar to this in C++ with a thread that contains a reference to a resource and cleans it up when only it has a single reference remaining (from the cleanup thread), but I can't find any evidence of this being a library or part of any existing language.

# Answer
GC deals *with a predictable and **reserved*** resource. The VM has total control over it and has total control over what instances are created and when. The keywords here are "reserved" and "total control". Handles are allocated by the OS, and pointers are... well pointers to resources allocated outside the managed space. Because of that, handles and pointers are not restricted to be used inside managed code. They can be used - and often are - by managed and unmanaged code running on the same process.

A "Resource Collector" would be able to verify if a handle/pointer is being used within a managed space or not, but it by definition is unaware of what's happening outside it's memory space (and, to make things worse some handles can be used across process boundaries).

A practical example is the .NET CLR. One can use flavored C++ to write code which works with both managed and unmanaged memory spaces; handles, pointers and references can be passed around between managed and unmanaged code. The unmanaged code must use special constructs/types to allow the CLR to keep tracking of references being made to it's managed resources. But that's the best it can do. It cannot do the same with handles and pointers, and because of that said Resource Collector would not know if it's ok to release a particular handle or pointer.

edit: Regarding the .NET CLR, I'm not experienced with C++ development with the .NET platform. Maybe there are special mechanisms in place that allows the CLR to keep tracking of references to handles/pointers between managed and unmanaged code. If that's the case then the CLR could take care of the lifetime of those resources and release them when there all references to them are cleared (well, at least in some scenarios it could). Either way, best practices dictate that handles (especially those pointing to files) and pointers should be released as soon as they are not needed. A Resource Collector would be not-complying with that, that's another reason to not have one.

edit 2: It's relatively trivial on the CLR/JVM/VMs-in-general to write some code to free up a particular handle if it's used only inside the managed space. In .NET would be something like:

```
// This class offends many best practices, but it would do the job.
public class AutoReleaseFileHandle {
    // keeps track of how many instances of this class is in memory
    private static int _toBeReleased = 0;

    // the threshold when a garbage collection should be forced
    private const int MAX_FILES = 100;

    public AutoReleaseFileHandle(FileStream fileStream) {
       // Force garbage collection if max files are reached.
       if (_toBeReleased >= MAX_FILES) {
          GC.Collect();
       }
       // increment counter
       Interlocked.Increment(ref _toBeReleased);
       FileStream = fileStream;
    }

    public FileStream { get; private set; }

    private void ReleaseFileStream(FileStream fs) {
       // decrement counter
       Interlocked.Decrement(ref _toBeReleased);
       FileStream.Close();
       FileStream.Dispose();
       FileStream = null;
    }

    // Close and Dispose the Stream when this class is collected by the GC.
    ~AutoReleaseFileHandle() {
       ReleaseFileStream(FileStream);
    }

    // because it's .NET this class should also implement IDisposable
    // to allow the user to dispose the resources imperatively if s/he wants
    // to.
    private bool _disposed = false;
    public void Dispose() {
      if (_disposed) {
        return;
      }
      _disposed = true;
      // tells GC to not call the finalizer for this instance.
      GC.SupressFinalizer(this);

      ReleaseFileStream(FileStream);
    }
}

// use it
// for it to work, fs.Dispose() should not be called directly,
var fs = File.Open("path/to/file");
var autoRelease = new AutoReleaseFileHandle(fs);

```
> 4 votes

# Answer
This appears to be one of the reasons languages with garbage collectors implements finalizers. Finalizers are intended to allow a programmer to clean up an object's resources during garbage collection. The big problem with finalizers is that they aren't guaranteed to run.

There's a pretty good write-up on using finalizers here:

Object finalization and cleanup

In fact it specifically uses the file descriptor as an example. You should make sure to clean up such resource yourself, but there is a mechanism in place that MAY restore resources that weren't properly released.
> 3 votes

# Answer
There are many programming techniques to help manage these kinds of resources.

* C++ programmers often use a pattern called Resource Acquisition is Initialization, or RAII for short. This pattern ensures that when an object that holds onto resources goes out of scope, it will close the resources it was holding on to. This is helpful when the object's lifetime corresponds to a particular scope in the program (e.g., when it matches the time when a particular stack frame is present on the stack), so it is helpful for objects that are pointed to by local variables (pointer variables stored on the stack), but not so helpful for objects that are pointed to by pointers stored on the heap.
* Java, C#, and many other languages provide a way to specify a method that will be invoked when an object is no longer live and about to be collected by the garbage collector. See, e.g., finalizers, `dispose()`, and others. The idea is that the programmer can implement such a method so that it will explicitly close the resource before the object is freed by the garbage collector. However, these approaches do have some issues, which you can read about elsewhere; for instance, the garbage collector might not collect the object until far later than you'd like.
* C# and other languages provide a `using` keyword that helps ensure that resources are closed after they're no longer needed (so you don't forget to close the file descriptor or other resource). This is often better than relying on the garbage collector to discover that the object is no longer live. See, e.g., https://stackoverflow.com/q/75401/781723. The general term here is a managed resource. This notion builds on RAII and finalizers, improving on them in some ways.
> 3 votes

# Answer
All memory is equal, if I ask for 1K, I don’t care where in the address space the 1K comes from.

When I ask for a file handle, I want a handle to the file I wish to open. Having a file handle open on a file, often blocks access to the file by other processes, or machine.

Therefore file handles must be closed as soon as they are not needed, otherwise they block other accesses to the file, but memory only needs to be reclaimed when you start to run out of it.

Running a GC pass is costly and is only done “when needed”, it is not possible to predict when anther process will need a file handle that your process may no longer be using, but still has open.
> 2 votes

# Answer
I would guess the reason why this has not been approached much for other resources is exactly because most other resources are preferred to be released as soon as possible for anyone to reuse.

Note, of course, your example could be provided now using "weak" file descriptors with existing GC techniques.
> 0 votes

# Answer
To check if memory is not longer accessible (and thus guaranteed not to be used anymore) is rather easy. Most other types of resources can be handled by more or less the same techniques (i.e., resource acquisition is initialization, RAII, and its counterpart of freeing when the user is destroyed, which links it with memory administration). Doing some kind of "just in time" freeing is impossible in general (check the halting problem, you would have to find out that some resource was used for the last time). Yes, *sometimes* it can be done automatically, but it is a much messier case as memory. So it relies on user intervention for the most part.
> 0 votes

---
Tags: garbage-collection, resource-allocation
---


# Question
Title: What is the complexity of a bracketed search using mediants?
I'm trying to estimate the complexity of an algorithm I've written for the Reko decompiler, where I'm trying to "undo" the tranformation done by a compiler to an integer division by a constant $x / n$. The compiler has converted the division into an integer multiplication and a shift: $(x * \lfloor 2^\beta / n \rfloor) \>\> \beta$, where $\beta$ is the number of bits of the computer's machine word. The resulting constant multiplication is a lot faster than a division in most contemporary architectures, but no longer resembles the original code.

To illustrate: the C statement

```
y = x / 10;

```

will be compiled by the Microsoft Visual C++ compiler to following assembly language

```
mov edx,1999999Ah  ; load 1/10 * 2^32
imul eax           ; edx:eax = dividend / 10 * 2 ^32
mov eax,edx        ; eax = dividend / 10

```

The net result is that the register `eax` will now have the expected value of `y` from the source code.

A naive decompiler will decompile the above to

```
eax = ((long)eax * 0x1999999A) >> 32;

```

but Reko aims to make the resulting output more legible than that by recovering the constant that was used in the original division.

The algorithm hinted at above is based on the description on this article in Wikipedia. First, the algorithm treats the constant multiplier as the scaled reciprocal $2^\beta / n$. It converts that to a floating point number $2^\beta r\_f$ and then scales it down by $2^\beta$ to $r\_f$, where $0.0 \< r\_f \<1.0$. The final, expensive step is to bracket the floating point value $r\_f$ between two rational numbers $a/b$, $c/d$ (starting with 0/1 and 1/1) and repeatedly compute the **mediant** $(a + c)/(b + d)$ until some convergence criterion is reached. The result should be the "best" rational approximation $r$ to the reciprocal $r\_f$.

Now, if the bracketing was being done with a typical binary search starting between the rationals $0/2^\beta$ and $2^\beta/2^\beta$, and computing the **midpoint** $(a/b + c/d)/2$, I expect the algorithm to converge in $O(\beta)$ steps. But what is the complexity of the algorithm if the mediant is used instead?

# Answer
> 4 votes
The relation between the Stern–Brocot tree and Farey sequences shows that if $0 \< p/q \< 1$ and $(p,q) = 1$ (i.e., $p/q$ is a reduced fraction) then $p/q$ is at the $q$th level of the tree. Since the running term of your algorithm is linear at the level in which you terminate, your algorithm takes time $O(q)$, where $p/q$ is the answer; but this is not so helpful.

You haven't specified what your stopping criterion is, but presumably you have some error threshold $\epsilon$. The question therefore is for which Farey sequence is it the case that adjacent terms are at distance at most $2\epsilon$ (and so every point is at distance $\epsilon$ from some point). Using the fact that the distance between adjacent fractions $p\_1/q\_1,p\_2/q\_2$ in a Farey sequence is $1/(q\_1q\_2)$, it is not hard to show that the maximal distance at the $q$th Farey sequence is $1/q$. Therefore if you are aiming at a distance of $\epsilon$, then your algorithm will run in time $O(1/\epsilon)$ in the worst case.

However, "most" adjacent fractions at the $q$th Farey sequence are at distance $O(1/q^2)$, and so on average you would probably expect a running time of $O(\sqrt{1/\epsilon})$ (unfortunately, this average is with respect to the input rather than the algorithm).

---
Tags: algorithm-analysis, runtime-analysis, numerical-algorithms
---


title: characteristic vectors for systems

text:
# Question
Title: characteristic vectors for systems
The question is motivated from a physics problem:

Let's first discuss the 1D infinitely long discrete system on a lattice, a system can look like:

system 1:

...(ABAC)(ABAC)(ABAC)...

this leads to its characteristic (or correlation) vector

```
<A>=0.5 this is the appearing frequency of character A
<B>=0.25
<C>=0.25
<AB>=0.25 this is the appearing frequency of character AB

```

....

system 2:

...(AB)(AB)(AB)...

this leads to its characteristic (or correlation) vector

```
<A>=0.5
<B>=0.5
<C>=0
<AB>=0.5
...

```

Such infinite characteristic vectors may be able to uniquely correspond to any 1D system (I don't have proof)... And by using this types of vectors (its finite version), it is easier to build machine learning models based on vectors instead of the structures itself.

This idea can extend to 2D, 3D systems naturally and this is what we call cluster expansion or generalized ising model....

The problem is, in physics, system is not necessarily in a lattice:

a description of a system (for 1D) is usually:

```
System 3:
1, its periodicity vector
2, atomic positions inside its unit cell

for example, a 1D system can be:
1, periodicity vector (3)
2, atomic positions (A at 0, B at 1.5)

```

this is ---A B A B---- system (atoms are only at specific coordinate, voids are everywhere else)

Is there any established theory/mathods in mathematics/computer science about its characters vectors/functions, that may be able to be used to build machine learning models? Thank you.

# Answer
> 1 votes
Yes. You want to look at the bag-of-words model and n-gram models.

The bag-of-words model corresponds to the part of your characteristic vector: namely, the parts `<A>`, `<B>`, `<C>` of your characteristic vector, i.e., the frequencies of a single letter. These are used as features for the ML algorithm.

n-gram models generalize this to a substring of length n. For each substring of length n, we count the frequency of that substring. These frequencies are again used as features. For instance, we'd have a feature for the frequency of `AB`, the frequency of `AC`, and so on.

In real-world computer science, we don't deal with infinite systems; we only deal with finite systems. (Our lifetime is finite, so a computer can only examine a finite portion of the input.)

---
Tags: machine-learning, features
---


# Question
Title: Algorithm for simplifying ANF or polynomials?
I have some digital logic circuits in Algebraic Normal Form, and am limited to using XOR and AND logic gates.

For instance:

$B\_{out} = B\_1 B\_2 \oplus B\_1 B\_3$

I was wondering, are there any algorithms to simplify ANF to use a smaller number of gates? I'm looking to minimize ANDs specifically.

The above equation would ideally become this:

$B\_{out} = B\_1 (B\_2 \oplus B\_3)$

Since AND and XOR act like multiplication and addition respectively, it also seems like the answer could be in algorithms which minimize operations in polynomials. If that is the case, I'm specifically looking to minimize multiplications (which is the equivelant of ANDs in ANF).

One person suggested i use a Karnaugh map, but am unsure how (or if it's possible) to use a Karnaugh map with XOR/AND instead of OR/AND. I could convert OR/AND back and forth to XOR/AND terms as needed, but in that case I don't believe the result is garaunteed (or likely) to be minimal anymore.

Are there algorithms for this? I feel like there has to be, but I haven't been able to find any.

# Answer
The algebraic normal form (ANF) is unique. You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one. Once you've found it, that's it; there's no other, "simpler" ANF for the same formula.

Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates. In general, that circuit won't necessarily be in algebraic normal form. (For instance, $B\_1 (B\_2 \oplus B\_3)$ is not in ANF; the ANF of that formula is $B\_1 B\_2 \oplus B\_1 B\_3$.) That's called "logic minimization" or "logic synthesis" or "circuit minimization". Most prior work has considered how to use a gate basis of NAND or {AND, OR, NOT}; you are looking for an algorithm that uses the basis {AND, XOR}.

If you want to minimize the total number of gates, I'd suggest you do a literature search on the literature on logic minimization, looking for methods that work with an arbitrary basis, or that work with the basis {AND, XOR}. (One possibly buzzword or phrase to search for is exclusive-or sum-of-products minimization; this covers the special case of circuits that have multi-input AND gates on the first level and a single multi-input XOR gate at the second level.)

In general, essentially all of these circuit minimization problems are NP-hard, so you shouldn't expect any efficient algorithm that will always work. Instead, people rely on heuristics that sometimes work or are sometimes efficient.

You can find people who have studied a similar problem in the cryptography world, because Yao-style garbled circuits naturally support AND and XOR gates. Cryptographers have studied how to implement various functions efficiently using only AND and XOR gates. However, in that world, for various reasons we can make XOR gates effectively free, so they generally try to minimize the "multiplicative complexity", i.e., the minimum number of AND gates needed in any circuit over the basis {AND,XOR}. I couldn't tell whether that was what you wanted or not. If it is, you might enjoy the following page, which lists circuits of minimal multiplicative complexity for a variety of functions of cryptographic interest:

http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html

Perhaps this will help you articulate a more precisely defined question.
> 4 votes

---
Tags: boolean-algebra, digital-circuits
---


title: Push relabel why return back to source

text:
# Question
Title: Push relabel why return back to source
In push relabel algorithm, at the end excess at any nodes is pushed back to source by raising height of those nodes above the height of source. Why is this done? In CLRS it's mentioned:

> To make the preflow a “legal” flow, the algorithm then sends the excess collected in the reservoirs of overflowing vertices back to the source by continuing to relabel vertices to above the fixed height |V| of the source. As we shall see, once we have emptied all the reservoirs, the preflow is not only a “legal” flow, it is also a maximum flow.

What does it mean to say "to make preflow a legal flow". Could someone elaborate on the same.

# Answer
> 1 votes
Inspecting the correctness proof and/or executing any non-trivial example, you'll note that push-relabel algorithms are different from Ford-Fulkerson and variants in that they *do not maintain a flow*; that's just not part of the invariant, and it's *blatantly* violated right at the start.

This whole "push flow to the sink, then push the excess back to the source" idea is only that: an idea. The algorithm does not *really* work like that, always. But it's still useful.

Once the "wave" reaches the sink $t$, it saturates the cut $V \setminus \\{t\\}$. You still have vertices with excess left¹, though; the *conservation of flow* property is violated. This has to be remedied before we can terminate with a flow -- hence the "push flow back to the source" phase.

---

1. Whenever the cut $V \setminus \\{s\\}$ is not by coincidence a min-cut.

---
Tags: algorithms, graphs, max-flow
---


# Question
Title: Understanding the P2||CMax scheduling problem
I have a problem with understanding the $P\_2 \mid \mid C\_\max$ problem which is also known as Tasks Scheduling on Multiple Processors.

In fact, in my case I need only one processor (but the problem is usually described for 2 or more so let it be). I understand what is all about: given a set of tasks with constant delay time and priority the algorithm should find the best permutation of them so that the total delay time is the smallest one.

And now is my question: if the delay is constant for each task, so how come different permutations provide different total delay?

# Answer
> 1 votes
Taking apart the notation, here is what we have:

* Two identical machines.
* $n$ jobs with equal duration $p$.
* No release dates or deadlines, i.e. $r\_i = 0$ and $d\_i = \infty$ for all $i$.
* No extra features.
* Objective function is maximum completion time.

It is true that all schedules *without idle time* have the same completion time in this setting. However, it still takes linear time to actually write down a schedule.

I guess this an easy exercise that is supposed to get you accustomed to notation and working in the model, and will maybe be extended to more complicated $\beta$.

Also, algorithms for this problem may be used as a *subroutine*, for instance for computing lower bounds in branch-and-bound algorithms for $P\_2 \mid \beta \mid C\_\max$ problems with non-trivial $\beta$.

*Note:* The number of processors can make the (conjectured) difference between polynomial and NP-complete complexity.

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: Cover points with minimal number of spheres of fixed radius
I have a set of k n-dimensional points:

P1(x11, x12, ..., x1n), P2(x21, x22, ..., x2n), ..., Pk(xk1, xk2, ..., xkn).

A distance D(Pa, Pb) is defined between any two points, which satisfy usual properties:

1. D(Pa, Pb) \>= 0
2. D(Pa, Pb) = 0 \<=\> Pa = Pb
3. D(Pa, Pb) = D(Pb, Pa)
4. D(Pa, Pc) ≤ D(Pa, Pb) + D(Pb, Pc)

What is the algorithm to find areas in which these points aggregate?
More specifically, given a radius R find the smallest set β of n-dimensional "balls" B(C) such that every point lies inside at least one of the balls:

ⱯPa ƎB(C) ∈ β =\> D(Pa, C) ≤ R

There is definitely more than one solution (in most cases a ball could be moved a little so that it would still contain the points) and probably there is something else I am missing. But I need an algorithm that would provide at least one solution.

Example:

If
k = 5, n = 2, R = 2, D(Pa, Pb) = euclidean distance on a plane
P1(0,0), P2(1,1), P3(4.5, 4), P4(-4, 1), P5(4,4),

Then
B1(0.5, 0.5) (contains first two points), B2(-4,1) (contains only 4th point), B3(4,4) (contains 3rd and 5th points)

# Answer
> 2 votes
Construct a graph. Represent every point by a node and connect two nodes with an edge if the distance of the represented points is $\leq R$.

Then, a minimial clique cover of the graph tells you which points should belong to the same sphere, one per cluster; pick the center of each set as center for the sphere.

Unfortunately, Minimal Clique Cover is NP-hard so no efficient algorithm is known for it. There may be algorithms suitable for your application in the literature, though.

---

Does it get any better? I don't have a proof, but this feels like a clustering problem to me which tend to be NP-hard. You may want to try and apply the ideas of hierarchical clustering.

---
Tags: algorithms, optimization, computational-geometry
---


# Question
Title: Training a HMM with Baum-Welch gives different results across runs
I am running a Baum-Welch HMM algorithm (in R). The sequence vector contains a series of observations which have been gathered from a dataset where the data has 17 states.

I can successfully run the HMM algorithm and it converges without any problems when I set pseudo count to 1e-09, below that the algorithm fails.

My question relates to the Baum-Welch algorithm and local minima. When I run the algorithm and obtain the estimates for the emission matrix and transition matrix, I then use these as inputs to calculate the posterior probability of a sequence.

That is all fine except that when I redo all of the above (in a new R session) I get completely different posterior probability estimates. Is this because the BW algorithm is getting stuck in different local minima each time?

# Answer
> 2 votes
It is impossible to locate the issue for sure without inspecting the implementation and results in more detail than is ontopic here. For instance, numeric algorithms always have potential issues related to the precision of the used number format, especially when dealing with (very small) probabilities.

That said, two notes.

* Baum-Welch *does* only find local optima.
* *Insufficient training data* can cause parameter estimations to vary wildly.

So I recommend you try more training data if possible. Otherwise, just run the algorithm many times and pick the best model (according to the likelihood of the training data according to the resp. model) you find.

---
Tags: algorithms, machine-learning, numerical-algorithms, hidden-markov-models
---


# Question
Title: Isomorphism of a DFA and the minimal DFA
I have a DFA A, I minimize A and the minimized DFA obtained is M. My question is if in general A and M are isomorphic?

# Answer
No. If the result of minimizing was always isomorphic to the thing you started with, minimization would do nothing!

For a concrete example, consider any automaton with more than one state, which has every state accepting. This automaton accepts $\Sigma^\*$ and is not isomorphic to the minimal automaton for that language, which has just one state.
> 4 votes

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


# Question
Title: Find all possible subset pairs in an array having equal average
Given an positive integer array with distinct elements, find all possible subset pairs having equal average. How to do this ?

Example: arr={5,10,6,7} Ans: {7},{5,6,10}

Exp: average of first subset=7 average of second subset=(5+6+7)/3=21/3=7

(two subsets for the array which when combined must have all the elements non repeated in the array). Problem is to find all possible pairs and print them. How to do this?

PS: I am not posting my homework stuff and i am learning algorithms. I couldnt find any approach to solve this.

# Answer
> 2 votes
I'm going to take HEKTO's suggestion that you mean that we're decomposing the set into a partition. We start with the observation that in any such decomposition, if the two subsets have the same arithmetic mean, then they must each have the same mean as the original set. To see this, suppose we have decomposed the set into the subsets $|\left\\{x\_i\right\\}| = a$ and $|\left\\{y\_j\right\\}| = b$ where $a + b = n$. If the two subsets have the same average then: $$\frac{\sum\_{i=1}^a x\_i}{a} = \frac{\sum\_{j=1}^b y\_j}{b}$$ $$\sum\_{i=1}^a x\_i = \frac{a}{b}\sum\_{j=1}^b y\_j$$ Also, observe that: $$\frac{\sum\_{i=1}^a x\_i}{a} = \frac{(1+a/b)\sum\_{j=1}^b y\_j}{n}$$ Just distribute the sum on the right and substitute our previous result and you'll see that the average of the $x\_i's$ are equal to the average of the whole set.

So, we've elminated a whole lot of partitions for us to look at. I would map each element of the set, $x$, to $x-\mu$, and now we require just that the sum of the elements in a chosen subset add up to 0, and I think a fairly standard dynamic programming approach will work from here.

---
Tags: algorithms, arrays, enumeration
---


# Question
Title: Design an NFA to accept a, ad, abc, abd, but not e, abcd?
I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that?

**Updated** I modified the diagram in another attempt:

# Answer
This is the correct answer for the specified specification:
> 0 votes

# Answer
Your automaton has *loops* so it accepts an infinite language.

For finite languages $\\{w\_1, \dots, w\_n\\}$, it's easy to write them as regular expression

$\qquad w\_1 \mid \ldots \mid w\_k$

and apply Thompson's construction. If the resulting automaton is too ugly for your taste, determinize and minimize according to the canonical textbooks.

*Warning:* Determinizing automata for finite languages can blow up automaton size exponentially.

Note how this approach scales neatly to more concise representations of finite languages and even infinite languages -- all you need is a regular expression. Or any other formalism equivalent to finite automata, as the proofs of equivalence are usually constructive.
> 2 votes

# Answer
Just make an automaton that looks like a tree, for each state splitting into the possible letters.

In data structure terminology such a tree with leters on edges is called a trie, as in re-trie-val.
> 1 votes

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: In the learning theory version of Occam's razor, why can't I just declare whatever hypothesis I want to be "shortest"?
Occam's razor states that shorter explanations (formally speaking, hypotheses) are more likely to be correct. Indeed this can be formalized: for a hypothesis class $\mathcal H$ one may ascribe representations to each hypothesis and take their literal length as strings. The shorter ones are more correct. But the problem is I can just rearrange the language to make perverse hypotheses shorter, at which point they will be more likely. This seems contradictory. What gives?

# Answer
> 1 votes
There are several ways to formalize Occam's razor in learning theory, and they yield theorems that are powerful. However, these theorems do not obviate the need for inductive bias, nor do they create it. That would be like asking a computer program to create entropy. They do not create the ghost in the machine. What they *do* provide is a way to formalize inductive bias and provide useful theorems for what one may conclude about a set of hypotheses weighted with inductive bias.

If you get "lucky" and the inductive bias you encode happens to match the real world - which you believe is prone to happen if you subscribe to Occam's razor out-of-universe - then the theorems will do a very good job of teasing out the matching hypothesis and will even know how to make tradeoffs between good, short hypotheses and excellent, less-short hypotheses. They will then provide a bound on the error.

What if you are living in a Kuhnian paradigm shift and you are not sure which of two sets of inductive biases is better? Will Occam's razor help you? Yes and no - if you have twice the data you can study both just as before but "twice the data" is of course asking for more information to enter the system. So they cannot magically decide between Newton and Einstein.

One presentation of Occam's razor, from *Understanding Machine Learning* as Theorem 7.7 is the following. It is a weaker presentation in that it is designed for nonuniform agnostic PAC learnability, which is quite weak, in that no perfect hypothesis can ever be returned. So the conclusions will also be weak.

> Let $\mathcal H$ be a hypothesis class and let $d:\mathcal H \rightarrow \\{0,1\\}^\*$ be a prefix-free description language for $\mathcal H$. Then, for every sample size $m$, every confidence parameter $\delta \> 0$, and every probability distribution $\mathcal D$, with probability greater than $1 - \delta$ over the choice of $S \sim \mathcal D^m$, we have that $$\forall h \in \mathcal H, L\_{\mathcal D}(h) \leq L\_S(h) + \sqrt{\frac{|h| + \ln(2/\delta)}{2m}}$$ where $|h|$ is the length of $d(h$).

This gives rise to the Minimum Description Length learning paradigm: For $\mathcal H, \mathcal D, d$ as above and a loss function, output the hypothesis $h$ that minimizes $L\_S(h) + \sqrt{\frac{|h| + \ln(2/\delta)}{2m}}$, i.e. the empirical loss plus the estimation error given by the theorem.

So by itself the theorem isn't making any claim about which hypothesis is best. It's actually making a much more boring claim that short hypotheses are *easy to estimate well*. It is possible to estimate a hypothesis $h$ up to an error factor of $O(|h|^{1/2})$ (where $O$ holds $m,\delta$ constant), and moreover, it is possible to do this for *all* hypotheses *simultaneously*. You can get each and every error estimate and only degrade the quality of the estimate in $O(|h|^{1/2})$.

Now I will convince you this is not trivial. Bear in mind at the other extreme, if you have a single hypothesis $h$ and you want to estimate its error, that's actually really easy to do on a small number of examples. It's the question of determining the weight of an unbiased coin by flipping it a few times, which is given by the Hoeffding/Chernoff bounds. Spoiler alert, you can achieve an estimation error of $\sqrt{\frac{\ln(2/\delta)}{2m}}$ with probability $1-\delta$. In above notation, that's $O(1)$ in $|h|$. All you were trying to do in the Theorem, for all $h$ equipped with some length function, is estimate the error and you achieved $O(|h|^{1/2})$ but here you achieved $O(1)$. What gives?

Let's try estimating for $1000$ hypotheses and try to achieve an estimation error of $10\\%$ with probability $99\\%$ just by using a simple Hoeffding bound. We calculate we need $265$ examples to achieve this. Not bad. So the first hypothesis we estimate within $10\\%$ with probability $99\\%$. The second hypothesis we estimate within $\10\\%$ with probability $99\\%$. But wait, that means the probability that either may fail could exceed $1\\%$. By basic probability we only know the probability both estimates succeed is at least $98.01\\%$.

And that's not good, because we have 1000 hypotheses. $.99^{1000}=0.004\\%$. Not good. And in the context of machine learning, if *one* hypothesis is estimated wrong, very often the hypothesis is an overfitter. So one failure is enough to ruin the whole model.

So if you *do* want to estimate 1000 hypotheses simultaneously, you will need many more examples (not too bad -- $\ln(2/\delta)$ does not grow too fast in $1/\delta$) to achieve this.

And if you have infinitely many, you simply cannot do it by naive application of the Hoeffding bound.

So the Theorem lets you achieve an $O(|h|^{1/2})$ estimation error for *all* hypotheses simultaneously. This is powerful.

What if you try to rig the game and take a complex hypothesis and rig it so its length is just $1$? Then you will get a good estimate for this hypothesis and a worse estimate for many others. The estimation error power is conserved. If you were interested in that hypothesis, you may have also just drawn 265 (or however many) examples and run a Hoeffding bound on it. This is no different.

And if you want to try two totally different schema, you may do exactly that, but you will need a tighter $\delta$ to assure that *both* succeed. This is a serious mistake you can make when running a machine learning algorithm!

The MDL learner makes no guarantees about returning the best hypothesis. It guarantees to return one that solves a particular set of bounds. That particular set of bounds incorporates "out of universe" Occam's razor, your *own* inductive bias as the learner or programmer or source of entropy, and will formalize that inductive bias into a set of bounds that will focus more attention onto "simpler" hypotheses, and if your inductive bias is on track, they will output aggressive error bounds on the hypothesis. I reiterate this is the nonuniformly PAC learnable model, so it's too much to ask for a guarantee on the resulting hypothesis. In that sense MDL is weak, as it must be.

A finite PAC formulation of Occam's razor is:

> Fix $\mathcal H$ and fix $\epsilon, \delta$. Suppose there exists a finite $\mathcal L \subset \mathcal H$ with the following property: Take $m \geq \frac1\epsilon(\ln|\mathcal L| + \ln(\frac1\delta)$. If for every $S \sim \mathcal D^m$ there is an $h \in \mathcal L$ so that $h$ is consistent with $S$, then $h$ is $\epsilon$-accurate and $\delta$-confident, so $\mathcal H$ is PAC learnable with this algorithm.

i.e. if a *small* hypothesis class can consistently represent *pretty large* sets of examples, then it is PAC. This is another version of Occam's Razor that, being in a PAC setting, is stronger than the nonuniform PAC discussion above: if the hypothesis class is surprisingly rich for how surprisingly small it is, then it actually describes the world accurately. But it demands a lot, as a real-world machine learner would be pressed to find a noiseless set of data that clean, and I'm not sure if this particular "Occam's razor" theorem generalizes to harsher terrain.

---
Tags: learning-theory, philosophy
---


# Question
Title: Turing machine states, lost in the jungle
There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- inaccessible states in a Turing machine. These are simply defined (look at page 43 here if you need a source) as states that are never reached.

The definition I linked to is accompanied with a state graph that shows an obviously inaccessible state. Simplified:

```
(q0)-1->((q1))<-0,1-(q2)

```

If `q0` is the start state, `q2` is obviously inaccessible. This is analogous to the deliberately-disabled code that was the premise of the EL&U discussion.

But I'm wondering about those states that are inaccessible, but you will never know it, because they're just lost in the jungle.

These states all have a path from the start state in the machine's state graph. But no matter how long the machine runs, the particular combination of state and symbol to make the number transition into that state never appears.

For some of these states, static analysis can determine if they're inaccesssible.

For the rest, no analysis will ever be able to determine if the state is ever reached. For example, if you could determine whether every halt state is reached or not, you would have just solved the (unfortunately-named, but don't get me started) Halting Problem. Let's leave out states that machines reach serendipitously if you run them long enough.

Is there a more specific term than 'inaccessible state' for this? (It's a shame 'inaccessible states' can't mean specifically this; it would have been a nice parallel with inaccessible sets from set theory.)

# Answer
> 1 votes
The only terms I have seen used with any consistency are "dead" and "unreachable".

There is also the dual, "unproductive" states. This term comes from formal grammars and means that you have a state/non-terminal from which you can not reach a final state/terminal string.

# Answer
> 1 votes
There is no such thing as a state that no static analysis can determine is inaccessible. For any Turing machine and any state that is actually inaccessible, there exists a static analysis algorithm that can determine that the state is inaccessible.

Perhaps what you are thinking of is that there is no static analysis algorithm that can identify all inaccessible states: for any static analysis algorithm, there exists a Turing machine with a state that is actually inaccessible but that the algorithm can't tell is inaccessible. That's not the same thing. The order of the quantifiers matters.

Therefore, you're asking for the name of a thing that doesn't exist. There is no such name. I'm afraid the only way to give a satisfactory answer to the question is to un-ask the question.

---
Tags: terminology, turing-machines, automata, computation-models
---


# Question
Title: Getting maximum number of pairs in a set
I'm sorry if the title is unclear, I didn't know how to name this question.

I have a problem where I have an array of numbers with positive integer values. For a pair of these integers to be considered valid, they should follow the format a^2 + b^2 = x^2, where a and b are the integers, and x is any whole number.

What I need to do is to find the maximum number of pairs that can be used **concurrently** (for example, if I have numbers {3, 4, 4}, the answer would be 1, even though there are two valid pairs (3 and the first 4, as well as 3 and the second 4), because we can not use both of these pairs at the same time.

Can anyone point me in the right direction toward solving this problem without brute-forcing all the combinations?

# Answer
Your problem is an instance of maximum matching, for which there exist efficient algorithms. The vertices in the graph are the entries of the list, and the edges correspond to allowable pairs.
> 3 votes

---
Tags: algorithms, optimization
---


title: Closest pair of points in a Plane

text:
# Question
Title: Closest pair of points in a Plane
I want to write an algorithm to find the closest pair of points among n points in an XY-plane. I have the following approach in my mind:

1. Find the minimum x co-ordinate(minX) and minimum y(minY) co-ordinate.
2. Name the point origin= (minX,minY)
3. Find the distance of all points from this origin and store it in a vector dist\[\].
4. Sort the vector dist\[\].
5. Traverse through the vector dist and for each i=1 to n-1, do dist\[i+1\]-dist\[i\] and keep track of the minimum of these and the pair that form this minimum.
6. Return minimum and the pair.

I am not sure if this algorithm would work because of how triangle inequality works.

Any help on why this algorithm should/should not work?

# Answer
> 5 votes
**No, your approach will not work**

Let $O$ be your chosen origin. Let $A$, $B$ be two of your other points. $OAB$ form a triangle.

The vector you have in mind would contain the distances $\overline{OA}$ and $\overline{OB}$. You can not determine the distance $\overline{AB}$ using only the two other sides of the triangle. You would need at least one of the angles for that.

As for a concrete counter example:

$O = (0,0), A = (0,2), B = (0,5), C = (2,0)$

so your vector would be:

$\overline{OA} = 2, \overline{OC} = 2, \overline{OB} = 5$

The differences are:

$\overline{OA}-\overline{OC} = 0$

$\overline{OC}-\overline{OB} = -3$

$(C, B)$ forms the minimum of but the closest pair is $(A, B)$ with a distance of 3.

# Answer
> 0 votes
I think your algorithm doesn't produce the correct results, because, as you mentioned, two points might have a close distance from your computed origin, but that doesn't mean that there are no two points that are closer.

I'm not sure, but I think there is no correct algorithm faster than $O(n^2-n)$, which is what you get when comparing them all with each other.

You can use an approximation, though. You could divide the space in sections and then compare only the vertices that fall into the same section. The problem is now to find the best division of the space.

# Answer
> 0 votes
Just a minor improvement to comparing each point with each other point: Sort the points in x order. Then you take the first point. You compare it with other points sorted in x order. However, if you found the closest pair of points so far at a distance d, you can stop that search as soon as the distance in the x direction alone is larger than d. To make the search more efficient, check the square of the distance (which is dx^2 + dy^2) instead of the actual distance, avoiding calculation of a square root.

This should be nowhere near O (n log n), but substantially better than O (n^2).

---
Tags: algorithms, computational-geometry
---


# Question
Title: How to prove LTL-formulas true for all paths?
I'm quoting a question from my homework which I don't understand its wording.

Also, I'm not looking for an answer for my problem, I just want to be pointed at some articles/tutorials/reading/tips to solve them.

```
Gp ⇒ (p U q) U p
(p U q) ∧ (q U p) ⇔ p ∧ q
Fp ⇔ F(Xp)
X(Fp) ⇔ F(Xp)
(p U (q ⇒ ¬Xq)) ∧ (FGq) ⇔ p U (Gq)

```

They ask me to prove if these formulas are true for all paths but it seems like they want me to prove them to be equivalent instead.

# Answer
> 1 votes
The statements you wrote are tautologies, i.e. they are always true. I will give you an example proof for the arguably easiest statement $FXp \leftrightarrow XFp$ so you see how you could do it yourself for the others. Also, it would be good to know if you are working on finite or infinite paths. I am going to use infinite paths here because that is more common as far as I know.

The statement says "There is a point in the future so that at the next position $p$ holds if and only if there is a point in the future other than the current point at which $p$ holds.

We can describe the path with the single predicate $p$ by a set $A \subseteq \mathbb{N}$ at which $p$ is true, and $\mathbb{N} \setminus A$ at which $p$ is false. Let $n \in \mathbb{N}$ be any position.

If $n \models FXp$, this is (by definition) equal to: there is a position $m \geq n$ such that $m \models Xp$, which is equal to $m+1 \models p$, which is equal to $m+1 \in A$. In other words: $n \models FXp$ if and only if there is an $m \geq n$ such that $m+1 \in A$.

If $n \models XFp$, this is equal to $n+1 \models Fp$, which means there is an $m \geq n+1$ such that $k \models p$, so $k \in A$. Again, this means $n \models XFp$ if and only if there is an $k \> n$ such that $k \in A$.

You can see that these two statements are clearly equivalent if you choose $k = m+1$. Therefore, $n \models FXp$ iff $n \models XFp$.

---
Tags: model-checking, linear-temporal-logic
---


# Question
Title: How to find several rectangles with minimum area to cover the red cells
In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) and Figure 1(c) are two ways. Obviously, (c) is a better way due to the smaller sum of area the green rectangles . Besides, the side length of these rectangles should be at least two unit length, for example, the green rectangles in Figure 2 are not allowed. The rectangles can overlap.

How to do this effectively? Is there any algorithm to do this?

I have a simple idea, firstly, use the K-means algorithm to divide these red cells into K clusters, then for each cluster, find a bounding box(rectangle) to cover it. But the sum area of these rectangles may not be small.

# Answer
The way I created the pictures in my comment is by Integer Linear Programming, specifically the following model:

$\text{minimize } x \cdot area \\ \text{for each red cell } (i,j): \\: \sum\_{k \in covers(i,j)} x\[k\] \ge 1 \\ x \in \\{0, 1\\}$

Where the decision variables `x[i]` refer to whether or not to use rectangle `i`, `covers(i, j)` is the set of rectangles that contain the cell `(i, j)`, `area` is the vector of the areas of the rectangles, and the set of rectangles used is all 2x2, 2x3, 3x2 and 3x3 rectangles that fit on the grid and contain at least one red cell. You can use a slightly smaller set, for example it is never necessary to use a piece that's bigger than 2x2 that covers only 1 red cell, it could always be replaced by a 2x2 piece and give a better solution. Any rectangles of other legal sizes can be constructed from these pieces so they can be left out.

Actually even fewer rectangles can be used. For example, a rectangle that can be replaced by a smaller rectangle without uncovering any red cells is redundant. There is also the case where a 3x3 can be replaced by 2 2x2 rectangles, that potentially overlap, such that they together cover (at least) the same red cells, making the 3x3 redundant.

Experiment shows that presolving removes almost all columns (for relatively sparse problems), suggesting that it should be easy to a-priori not-generate many of them. I have not looked into that too deeply yet.

Despite ILP being NP-hard, large instances such as this or even this were solved in a couple of seconds. Maybe there is also an inherently efficient way though, I'm not sure.
> 2 votes

---
Tags: algorithms, optimization, computational-geometry
---


# Question
Title: Finding the mistake(s) within this "proof" of NP being closed for complement
For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some help:

> *Lemma*:
>
> If $L \in NP $, then $ \bar{L} \in NP $
>
> *Proof*:
>
> * Let N be a non-deterministic Turing machine, which accepts L in polynomial time.
> * Swap all final states of $N$ with non-final states and vice-versa.
> * This new Turing machine $N'$ does now accept $\bar{L}$ in polynomial time.
>
> Therefore $\bar{L} \in NP$

I have doubts that simply swapping non-final and final states within $N$ will produce a $N'$ with the proposed properties, but how can I show this?

# Answer
> 4 votes
You just need to show that swapping final and non-final states doesn't complement the language accepted by an NTM, e.g., by showing that, for at least one NTM $N$ (which you can construct to have whatever properties you need), there is a string that is accepted by both $N$ and $N'$, or rejected by both.

---
Tags: complexity-theory, closure-properties, np, co-np
---


title: Verifiers equivalent classes

text:
# Question
Title: Verifiers equivalent classes
This is a HW question, so Im not expecting full solutions or anything, but would love some direction. Also English is not my first language, so I apologize in advance.

We define a new class of languages - VNL:

> all languages L s.t there exists M - a DTM with:
>
> * an input-read-only tape.
> * a "witness" tape which is a "one-time" read-only and can be read only as stay/right (the tape head cant move left).
> * a work tape which is read/write.
> * Also there exists p a polynomial s.t. for every w $\in \\{0,1\\}^\*$: $w\in L\ \iff\ \exists u\in\left\\{ 0,1\right\\} ^{p\left(\left|w\right|\right)}:\ M\left(w,u\right)=acc$
> * M is of O(log(|w|)) space complexity (where w is the input).

Now we need to prove VNL=NL. I think I managed the VNL$\subseteq$NL direction:

> Let L$\in$VNL. then there exists M a DTM as we described before.
> I then define a NDTM - $M\_L$ on input w: that runs M on w,u where u is randomly generated, bit by bit, everytime M wants to move right.
> It only needs to store an index to make sure u is of the right size, and that takes log(p(|w|) space, which is still logarithmic space complexity, and also running M is logarithmic. I also explain why M meets the other demands (but as they are somewhat trivial, I don't write them here to keep this post a bit shorter).

I have two questions:

> 1. I'm not entirely sure how to do the other direction (NL$\subseteq$VNL). What I tried so far was: take L$\in$NL. $M\_L$ is the logarithmic NDTM for it. I define M (of our new type) to treat the "witness" tape as a series of configurations. Somehow I'm supposed to verify its a legitimate configurations series resulting in M accepting w. Perhaps draw 2 consecutive configurations to the work tape and somehow verify the the transition between them is legitimate? Would love help with that.
> 2. For another section of the question we remove the demand that the witness tape is read only to the right (which means I can read it as many times as I want). We're supposed to determine to which class VNL equals now. I thought about NP, but encountered some difficulties during the proof. Would also love help with that.

Thank you!

# Answer
To your first question, suppose your non deterministic machine has two transition functions $\delta\_0,\delta\_1$ (if you allow arbitrary number of transitions, then you can construct an equivalent Turing machine with only two transitions by adding more states). In that case, it is intuitive how to use the one time read witness. Read $w\in \\{0,1\\}^{p(|x|)}$ as a computation sequence, i.e. the $i'th$ bit is $0$ if $\delta\_0$ is used and $1$ otherwise. Follow the computation described by $w$, and accept iff the original non deterministic machine accepted in this computation. I leave it to you to complete the details.

As for your second question, the class generated is indeed $NP$. Obviously $VNL\subseteq NP$, so it remains to see why $NP\subseteq VNL$. Let $L$ be some language in $NP$, so we have $L\le\_p SAT$, where the reduction can be computed in logarithmic space (verify that the reduction used in the proof of Cook-Levin's theorem can indeed be computed in logspace). Let $f$ be the reduction from $L$ to $SAT$ computable in logarithmic space. Given $x\in \Sigma^\*$, we would like our witness $w$ to be a satisfying assignment for $f(x)$, since we can verfiy an assignment in logarithmic space. The problem is that $|f(x)|$ is polynomial in $|x|$, so we cant write it in our work tape. You can solve this by having $f(x)$ provided in the witness (along with an assignment), and your machine could verify for all $1\le i\le |f(x)|$ that $w\_i = {f(x)}\_i$. Luckily, since $f$ is computable in logspace, you can verify that the witness provided the correct $f(x)$, and check if the assignment satisfies $f(x)$.
> 6 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Why injection into sum type apparently leads to ambiguity?
I have been reading Benjamin Pierce's *Types and Programming Languages*, plus a couple of course notes on type systems and typed $\lambda$-calculus, and there is one thing I don't get: it seems that everybody defines sum types in the same way, and they way the language is extended to accommodate this new type includes the following typing rules:

* if $\sigma$ and $\tau$ are types, then $\sigma+\tau$ is a type
* if $M$ is of type $\sigma$, then $\operatorname{inl} M$ is of type $\sigma+\tau$
* symmetrically for $\operatorname{inr}$, if $M$ is of type $\tau$, then $\operatorname{inr} M$ is of type $\sigma+\tau$.

However, suppose I have two sum types, $\sigma+\tau$ and $\sigma+\phi$, and also that $M$ is of type $\sigma$. Then it is not clear what the type of $\operatorname{inl} M$ is.

Is there something I missed, or is this really how sum types work? Because it would be quite easy to actually "fix" the definition to allow one to immediately infer the type of $\operatorname{inl} M$ in the example above -- just include the sum type in the annotation:

$\operatorname{inl\_{\sigma+\tau}} M$ is, of course, of type $\sigma+\tau$.

But this is not what is usually done. Why? (Or is it actually done, implicitly?)

# Answer
I think the key point here is $\sigma$, $\tau$ and $\phi$ are type *variables*, and not specific types. So, what the typing rule for $\operatorname{inl}$ says is that $\operatorname{inl} M$ is of type $\sigma + \tau$ **for any $\tau$**. The names of type variables don't matter, what matters is where else are you using the same type variable.
> 6 votes

---
Tags: programming-languages, lambda-calculus, semantics, type-inference, types-and-programming-languages
---


title: Finding the language generated for CFG

text:
# Question
Title: Finding the language generated for CFG
What language generated by the following context-free grammar 1) S------\> SaS | b i already know the answer to question one but to prove it would is be something like this: S -----\> SaaS -----\> baab which can also be express as the language b(ab)\* or (ba)\*b

Another question is what does | b mean does it mean substitute into S afterwards?

2) S ----\> AA

A----\> aA | Aa | b

So for this question how can i start this? Would it be like S----\> AA ----\> aAaA ----\> aAaAaA -----\> abababa ? SO the language would be (ab)\*?

# Answer
> 1 votes
The vertical bar indicates an alternative: $S\to SaS \mid b$ means there are two production rules in the grammar, $S\to SaS$ and $S\to b$. Since $b$ contains no variables it is like a final rule applied to a particular branch of the derivation-tree. But that does not mean the rule $S\to b$ has to be the postponed and applied to all occurrences of $S$ in the end.

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


# Question
Title: construct a dfa that accepts odd consecutive number of 0's and 1's
this dfa should accept only consecutive odd number of both 0's and 1's. example: 10001,1110001,10,01,011101.

How can I draw its diagram?

# Answer
Here are a couple of hints to get you started.

1. Could you make a DFA that accepts only $0, 000, 00000,\dotsc$? You can do it with a start state, a final state, and one other non-final state.
2. Obviously, if you can do (1), you can make a DFA that accepts only $1, 111, 11111,\dotsc$.
3. Merge the two DFAs into one with a common start state and appropriately link the two final states. You'll have a DFA that accepts all strings which have an odd number of consecutive $0$s followed by an odd number of consecutive $1$s, followed by ... or an odd number of consecutive $1$s followed by an odd number of consective $0$s, followed by ... , which is what you want.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Hamming error correction with non-uniform error correction capability
If I understood correctly, Hamming codes assume the uniform correction among all the bits. This means all the bits have the same weight in terms of correction.

Are there any error correcting codes out there that assume non-uniform error correction probability among the bits? For example, I want a error correcting code that corrects the first bit all the time, but it is fine to correct the second bit 90% of the time.

# Answer
The topic you want is Unequal Error Protection (UEP) codes. There are a number of constructions in this area and a google scholar search yields quite a few hits.

Intuitively, imagine partitioning your code into disjoint point clouds, where cloud centres are chosen by the more important bits, thus intra-centre distance is high, hence those bits are more robust to noise.

Some references:

On linear unequal error protection codes, B Masnick, J Wolf - IEEE Transactions on Information Theory, 1967.

Multilevel codes for unequal error protection AR Calderbank, N Seshadri - IEEE Transactions on Information Theory, 1993.

A more information theoretic perspective is the Borade et al paper here on the arXiV.

Lastly, Prof. Lloyd Welch published a nice paper on "Codes correcting selected error patterns", which I can't seem to find a reference to.
> 1 votes

---
Tags: error-correcting-codes, hamming-code
---


# Question
Title: Is there any merging procedure for multiple scenes taking from RGB-D to avoid noise?
To avoid the noise as much as possible, I'm planning to take multiple scenes from RGB-D then try to merge them ....

so is there any research papers , thoughts , ideas , algorithms or anything to help

# Answer
> 0 votes
Yes, one technique is known as super-resolution imaging. There's a rich literature on the subject, at least for RGB images. You could check Google Scholar to see if there has been any research on super-resolution for RGB-D images (e.g., from 3D cameras such as Kinect, Intel RealSense, etc.).

---
Tags: computer-vision
---


title: Hill Climbing Search

text:
# Question
Title: Hill Climbing Search
With the hill-climbing search algorithm, I do not quite understand how the algorithm can get stuck at "plateaus/ridges." Moving one step back, what exactly denotes a "maximum" or "minimum" in a problem? For instance, in the 8-queens problem, it is said that it hits a local minima 86% of the time. Can someone please elaborate more on how and what denotes maximas and minimas and given this, how the algorithm can get stuck at a plateau.

What I know so far is the following:

1. Expand the current state, find the best neighbor, and that becomes the new current state.
2. No looking beyond one step from where you are, no memory

# Answer
> 1 votes
Consider the general problem of maximizing such function $f$ on a domain $V$. Now suppose there is a graph $G=(V,E)$ on $G$. A *local maximum* is a vertex $v$ such that $f(v) \geq f(u)$ for all neighbors $u$ of $v$. A *global maximum* is a vertex $v$ such that $f(v) \geq f(u)$ for *all* $u \in V$. Hill climbing can get stuck at a local maximum which isn't a global maximum. Perhaps you can construct such an example yourself.

In the 8-queens problem, the domain $V$ is the set of chess boards with k non-conflicting queens on them for $k=0$ to $k=8$. There is an edge between two such boards if you can reach one from the other by placing one queen. The fitness function is simply the number of queens on the board. Simple hill climbing gets stuck if it ends up in a board with fewer than eight queens where no more queens can be placed, because there is no edge that goes to a board with more queens on it.

---
Tags: algorithms, optimization, search-algorithms, numerical-algorithms
---


title: Size of instance after reduction

text:
# Question
Title: Size of instance after reduction
A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time.

Reduction means transforming an instance of one problem $A$ to an instance of another problem $B$, and by using an algorithm that solves $B$ we can obtain the solution to $A$ for our original instance.

Is there any relationship between the size of instance before and after reduction? If for example the algorithm solving $A$ is $O(n^2)$ and our instance of $A$ of size $n$, what can we say about the instance size after reducing it to $B$, whose algorithm is $O(2^n)$ (the complexity of algorithms actually doesn't matter). Is it $n$ as well? Or maybe it is a polynomial of $n$?

The question is if the fact that a problem $A$ can be reduced to $B$ in polynomial time tells us anything about the size of the resulting instance (of problem $B$) with respect to the size of initial instance of $A$.

Why? It is known that

> If we had a polynomial algorithm for an $NP$-complete problem we could solve any other $NP$ problem in polynomial time

right? Because we just reduce $NP$ problem to $NP$-complete problem in polynomial time and solve it in polynomial time.

Let's say problem $A$ is $NP$ and problem $B$ is $NP$-complete. I've found an algorithm for $B$ that is $O(n)$ (polynomial). And let's say the size of our $A$ instance is $k$. If I reduced it to $B$ in polynomial time and got an instance of $B$ of size $n=2^k$, then the total time of solving it wouldn't be polynomial. So certainly the polynomial time reduction can't give an instance of size $2^k$, because if it could, then the quote above wouldn't be true.

# Answer
> The question is if the fact that a problem A can be reduced to B in polynomial time tells us anything about the size of the resulting instance (of problem B) with respect to the size of initial instance of A.

Yes, of course. If your reduction function $f$ has running-time function $T\_f \in O(n^k)$, then $|f(x)| \in O(n^k)$ -- a Turing machine can not write to more than one cell per execution step.

> Let's say problem A is NP and problem B is NP-complete. I've found an algorithm for B that is O(n) (polynomial).

Now you are rich, but go on.

> And let's say the size of our A instance is k. If I reduced it to B in polynomial time and got an instance of B of size $n=2^k$

As explained above, that can not happen.

> then the total time of solving it wouldn't be polynomial.

So what? Just because *one* reduction to *one* problem and using *that* one's algorithm does not yield a polynomial-time algorithm for $A$ does *not* imply that $A \not\in P$.

Plus, you never assume that $A \in P$ so there is very clearly no contradiction.

> So certainly the polynomial time reduction can't give an instance of size $2^k$, because if it could, then the quote above wouldn't be true.

That statement is correct, but your reasoning is flawed as explained above.
> 2 votes

# Answer
First of all, for your definition of NP-complete, we require the reduction to be polynomial time. This makes it so that if we could solve an NP-complete language, L, in polynomial time, we would have a polynomial time algorithm for all of NP by composing the polynomial time reduction with that algorithm for L.

Note that the size of the output of a reduction has to be less than the run time of the reduction. The biggest output possible given a fixed run time would be one where a Turing machine, M, prints to its output tape at every step.
> 2 votes

# Answer
The definition of P

*does* give its machines enough time to read the whole input, so we do
require that P reductions produce the whole output in a single execution
and
does *not* use parallelism, so P machines are unable to
output more bits than the amount of steps they run for

.
Thus, "the size of instance" after reduction is bounded above
by a polynomial in "the size of instance before reduction".

There are "reductions" from sufficiently-easy languages whose output size is always 1 bit:
For any target language L such that `1` is in L but `0` isn't, the "reduction"
can solve the input problem and then output `0` or `1` accordingly.
> 0 votes

---
Tags: complexity-theory, time-complexity, np-complete, reductions
---


# Question
Title: Partial path known in Single source shortest path problem
I'm using the A\* algorithm with a consistent heuristic on a graph to determine the shortest path.

If the algorithm is exploring a node $p\_1$ for which there is a existing knowledge about the optimal $k$ ($p\_q,p\_r,p\_t,p\_5$) successive nodes, then can we store $p\_5$ directly into the open list? Or do we have to store the intermediate milestones (each node in the known successive optimal nodes) into the open list?

Weights are positive real numbers.

# Answer
> 2 votes
Your question is strongly related to the idea of *macro-moves* which are defined as follows: $M(p, q)=\langle p, n\_1, n\_2, \ldots, n\_k, q\rangle$, i.e., as a list of successive states which are known to get to $q$ from $p$. Additionally, macro moves might guarantee that the path they store is also optimal, i.e., that the path $\langle p, n\_1, n\_2, \ldots, n\_k, q\rangle$ is the shortest path between $p$ and $q$. Let us denote such macro-moves as $M^\*(p, q)$.

In the following I'll assume you are interested in computing the optimal path from a start state $s$ to an arbitrary goal state $t$ ---as you actually mention the "shortest path" at the beginning.

So now, regarding your question:

1. In case that $M^\*(p,q)$ is known to be a subpath of the optimal path from $s$ to $t$, or if alternatively, it is known that the optimal path from $s$ to $t$ does not go through $p$, then you can safely substitute each generation of $p$ in OPEN by $q$ with a cost equal to the cost of the path to generate $p$ plus the cost of the path $M^\*(p,q)$.
2. In case none of the preceding conditions hold then you can still use the macro-moves but you have then to store each node in $M(p,q)$, but $p$ of course, into the OPEN list ---i.e., the intermediate milestones you mention.

Hold on! You might think then that the second case is a waste of time/space, but it ain't if you break ties in favour of nodes with larger $g$-values, i.e., while nodes in OPEN are sorted in increasing order of their $f$-value, breaking ties in favour of nodes with larger $g$-values place those nodes with larger $g$-values first ---within the same $f$-layer. This way, in case that an optimal path (as there might be several paths with the same cost and equal to the minimum cost) goes through $p$ there is an opportunity that you will find it without generating other descendants.

To see why, consider that a subpath of $M^\*(p,q)$ is part of the optimal path from $s$ to $t$, $\langle p, n\_1, n\_2, ...,n\_\ell\rangle$, such that $\ell\leq k$, and let $g(n)$ denote the cost of the path from $s$ to $n$ and $g(p, n\_i)$ denote the cost of the path $\langle p, n\_1, n\_2, ..., n\_i\rangle$ where $\langle p, n\_1, n\_2, ..., n\_i\rangle\subset M^\*(p,q)$. The second case suggests to insert into open $n\_1, n\_2, ..., n\_\ell$ each with a cost equal to $g(p)+g(p,n\_i)$, $1\leq i\leq\ell$. If the heuristic function is consistent (as you mention) there is a good opportunity that $f(n\_\ell)=f(n\_i)$, $\forall i, 1\leq i\<\ell$. Now, breaking ties in favour of nodes with larger $g$-values, $n\_\ell$ will be placed before the others so that A$^\*$ will expand it first. If $f(n\_\ell)$ equals the cost of the optimal path then A$^\*$ will find the optimal solution with out expanding nodes $n\_i$.

Maybe you think there are many "maybes and ifs" here but consider: first, breaking ties in favour of larger $g$-values is customary practice; second, inserting the intermediate states of $M^\*(p, q)$ causes no harm so that proceeding as in the second case is usually a good idea.

Hope this helps,

---
Tags: algorithms, graphs, shortest-path, graph-traversal, weighted-graphs
---


# Question
Title: What are the steps/tricks/tips to construct a Büchi automaton from a given language?
Let's say I have this language: $(a + bc)^∗((b + c)a^ω + (abb^∗)^ω)$

It seems pretty complicated, where should I begin with if I were to construct a Büchi automaton?

I've been doing it the following way with smaller language sets:

* a $^\*$ operator is usually a path coming from a node to the same node.
* a $+$ draws 2 branches

how would $^ω$ be represented? there are other operators, which I have not seen yet, what are they and how would they also be represented?

Pardon me if this is a silly question, but I'd rather ask than not knowing the answer ever.

Any help is greatly appreciated. Thang

# Answer
> 3 votes
You can construct an NBA for an $\omega$-regular expression $r$ by induction on the generating sequence of $r$, using the constructive closure properties of NBAs.

You can see some examples here

---
Tags: automata, buchi-automata
---


# Question
Title: How to use the concept of loop invariant to reduce errors in loops?
Most of time while writing loops I usually write wrong boundary conditions(eg: wrong outcome) or my assumptions about loop terminations are wrong(eg: infinitely running loop). Here is an small example where I got stuck several times, the example is a sub problem that I skinned out for solving insertion sort algorithm.

```
/**
 * Inserts the given value in proper position in the array.
 * @param array
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    // assert sorted(array, rightIndex)
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }
    array[j + 1] = value;
    // assert sorted(array, rightIndex+1)
};

```

**The mistakes that I did initially were:**

1. Instead of `j >= 0` I kept it `j > 0`.
2. Got confused whether `array[j+1] = value` or `array[j] = value`.

That time I don't have any tool to verify where I am doing wrong, fortunately on Googling I came to know about loop invariants.

To get hold of the above concept I thought to apply the concept here, although I am not mathematician but trying some equation I thought this would be good invariant.

$$array\[0...j\] \<= val \< array\[j+2...rightIndex+1\]$$

As far as I understood the concept, its a loop invariant because the inequalities contains the loop variable `j`. How to utilize this equation here?

Being naive at this concept I am stuck and don't know how to use this invariant in my loop. How to gain confidence about the correctness of my loop?

# Answer
I'm not terribly familiar with the topic, and as such let's discuss a simpler variation of your problem. In particular, rather than consider a sorted subarray, let's suppose our function is given a sorted array instead.

---

So we are given a value `e` and a sorted array `a[0..r]`, and our goal is to have the array `a[0..r+1]` sorted after insertion of `e`. For reference, let us introduce some abbreviations.

$$ Sorted \\; a\[m..n\] ∶≡ (∀ i : m..n • aᵢ ≤ aᵢ₊₁) $$

Now our program has precondition and post-condition

```
Pre : Sorted a[0..r] ∧ a = A₀
Pos : Sorted a[0..r+1] ∧ e ∈ a[0..r+1] ∧ a is a permutation of A₀ with e inserted

```

The `A₀` is used to make sure that no elements of `a` are deleted or rewritten; indeed, setting all elements of the array to `e` gives us a sorted array that contains `e`! But we can simplify matters by simply putting a constraint on the code: only array swaps are allowed.

```
Pre : Sorted a[0..r]
Pos : Sorted a[0..r+1] ∧ e ∈ a[0..r+1]

```

Now a usual way to obtain an invariant from the post-condition is to replace a constant with a variable and adding an equality to regain the post-condition, so let's try replacing 0 in `Pos` with `j` and add an equality for the two:

```
Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≈ 0

```

This clearly establishes the post-condition, so we're on the right track! Let's simplify it further by breaking the equality up:

```
Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≤ 0 ∧ 0 ≤ j

```

Now half of this is easily made-true by taking `j ≔ r+1` and `aᵣ₊₁ ≔ e` ---since `Sorted a[r+1..r+1] ≡ aᵣ₊₁ ≤ aᵣ₊₁` and `e ∈ a[r+1..r+1] ≡ aᵣ₊₁ ≈ e`--- and thus this half we take to be the invariant

```
P : Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ 0 ≤ j

```

and the rest we take to be the negation of the loop guard, and so our loop has condition

```
B : 0 ≤ j - 1

```

***Summarizing so far:*** if our loop has guard `B` and invariant `P`, then if the loop terminates we must have the guard is false and the invariant still holds, ie $Sorted\\; a\[j..r+1\] ∧ e ∈ a\[j..r+1\] ∧ j ≤ 0 ∧ 0 ≤ j$, and from this the post-condition is established!

To continue the derivation of our program, we need to the loop (whatever it is, since we have not yet found it) to terminate, since the above summary said `if the loop terminates`. The guard gives us that `j` is a positive value and so a good candidate for a bound on the number of iterations in the loop. It can be decreased by each iteration of the loop by incrementing it, `j ≔ j -1`, and so that is what we *try* do.

Of course the invariant, by definition, must be left-true by the body of the loop. In particular, assuming the invariant and the guard, we must show that the invariant still holds after execution of the proposed loop-body `j ≔ j -1`.

```
  P still holds after execution of j ≔ j - 1
≡⟨ definitions ⟩
  Sorted a[j-1..r+1] ∧ e ∈ a[j-1..r+1] ∧ 0 ≤ j-1
≡⟨ 0 ≤ j - 1 follows from B ⟩
  Sorted a[j-1..r+1] ∧ e ∈ a[j-1..r+1]
≡⟨ e ∈ a[j-1..r+1] ≡ e ≈ aⱼ₋₁ ∨ e ∈ a[j..r+1], and this follows from P ⟩
  Sorted a[j-1..r+1]
≡⟨ By P we know that Sorted a[j..r+1],
   so a[j-1..r+1] is sorted precisely when aⱼ₋₁ ≤ aⱼ ⟩
  aⱼ₋₁ ≤ aⱼ

```

So we need the decrement to be guarded by this condition. But what if this condition does not hold; ie instead we have aⱼ \< aⱼ₋₁? Then we can obtain the needed condition by swapping the indices and so the loop body becomes

```
if aⱼ < aⱼ₋₁ then swap(j, j-1);
j ≔ j-1;

```

So we've obtain a terminating loop and so our summary above means we are done. So the resulting program is:

```
j ≔ r+1;
aᵣ₊₁ ≔ e;
while 0 ≤ j - 1:
   if aⱼ < aⱼ₋₁ then swap(j, j-1);
   j ≔ j - 1

```

That is,

```
aᵣ₊₁ ≔ e;
for(int j = 0; 0 < j; j--)
   if aⱼ < aⱼ₋₁ then swap(j, j-1);

```

---

Let's try it out.

Given sorted array `a = [1,2,3,4,5]` and value `e = 3` we get $r = 5$ and so, letting | denote where we are looking in the array, the loop looks as follows:

```
j  a
6  [1,2,3,4,5 | 3]
5  [1,2,3,4 | 3,5]
4  [1,2,3| 3,4,5]
3  [1,2| 3,3,4,5]
2  [1| 2,3,3,4,5]
1  [|1, 2,3,3,4,5]

```

In particular, note that since the array is initially sorted, the moment we stop making swaps we no longer make any swaps at all and just decrement the counter. With this mind, we can be a bit perverse (for the sake of efficiency?) and write

```
aᵣ₊₁ ≔ e;
for(int j = 0; 0 < j; j--)
   if aⱼ < aⱼ₋₁ then swap(j, j-1) else return;

```

---

Hope this helps!
> 2 votes

---
Tags: correctness-proof, induction, loop-invariants
---


title: Monoalphabetic Cipher Key

text:
# Question
Title: Monoalphabetic Cipher Key
I am not sure how to get the key for the following Monoalphabetic Cipher question. This is a textbook question and I know the answer, but I juts dont know how they got the key.

Question:

> Decrypt the following Cipher texts, and give the key. (Note that the correct key is the Encryption key, so if F changes to H and F is the plaintext, then the key is “C”):
>
> (a) YRRYAIYRMLAC (b) DOBXQPZELLI

Answer: a) Text:`ATTACKATONCE` Key = `X` b) Text: `GREATSCHOOL` Key = `A`

Can somone please explain to me how to determine the key?

# Answer
> 1 votes
You try all 26 possibilities, and check which of them results in an English-looking test. In principle you can do the latter statistically, but in this case there are only 26 possibilities, so you might as well just look at all of them manually.

# Answer
> 1 votes
Instead of trying the 26 possibilities, you can use some statistics about the most common letter combinations (see e.g. http://scottbryce.com/cryptograms/stats.htm). The text are short for statistics, but have some double letters RR for (a) and LL for (b). The most common (and almost only) letter repetitions in English are `SS, EE, TT, FF, LL, MM, OO`, which reduces the number of trials to 7.

For the first 4 letters of (a), `YRRY`, mapping `RR`

* to `SS` leads to `ZSSZ..ZS....` : obviously bad
* to `EE` leads to `LEEL..LE....` : why not ? But transcribing the next letter `A` gives the bad `LEELN.LE..N.` which doesn’t look very English
* to `TT` gives the promising `ATTA..AT....`, which leads to the good decipherment.

That said, on so short text, it is difficult to make statistics, and you may end up testing all the 26 keys

---
Tags: cryptography, encryption
---


# Question
Title: how to calculate time complexity of non terminating loops
I'm studying about data structures and algorithms in that *Time complexity* and calculating time complexity of the programs.

I just wondered that how to calculate time complexity of non terminating loops such as infinite loops

# Answer
If the program runs forever, its running time is infinite. So, if it always enters an infinite loop, its running time is infinite.

This is a degenerate case. Normally we focus only on algorithms that are certain to terminate (but see footnote).

See also How to come up with the runtime of algorithms? and Is there a system behind the magic of algorithm analysis?.

---

Footnote: When studying randomized algorithms, this gets relaxed a bit, and we frequently look at algorithms that in principle could run forever if they keep getting an unlucky choice of random bits, but whose expected running time is finite. However, if you're just starting with algorithms, it's likely that you are dealing with deterministic algorithms, not randomized algorithms, so this is unlikely to come up.
> 14 votes

# Answer
Basically time complexity usage makes it easy to calculate the running time of a program and this complexity is depicted in Big-O notation. But since the loop never ends it has no "algorithmic time complexity" Trying to estimate such loop's complexity would be weird and of no good use as infinity is not a real number.
> -1 votes

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