title: What exactly is an algorithm?

text:
# Question
Title: What exactly is an algorithm?
I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, about ways to devise programs other than the ones taught in university.

Consider the factorial function. Typically we define this function like

```
 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

```

I'd call this an algorithm and have no doubt that this is the right way to do it. Then, i wondered "can i do this in constant time?", which let to the following idea: what if i had an array of integers where array\[n\] houses the factorial of n? Once this array is filled i could simply define fact as:

```
 int fact(int n)
 {
 return array[n];
 }

```

Still i cant seem to cal this an algorithm, even though it provides the correct result and operates in constant time O(1). Can this be called an algorithm? Otherwise, why not? I could argue that filling the array would require an algorithm to have operated at some time, even if it was in our brain in order for us to fill the array, but could this be the criteria? How are these aspects handled formally?

Note that this concept could be extended to any function operating over integers independly of its number of arguments, i would just have to use a matrix if the function had 2 arguments, or 3 if the function had 3 arguments, and so forth. Also, aren't these solutions used simply because of memory consumption?

Also, not that functions may also encompass any program with output, since i could find a way to index every single possible output that a program could provide.

As another exemple, consider the common use of an array: i allocate an array initially of size N, then i add elements to array by storing the value at index n and increasing n by one unit. Then, if i want to look for an elemento, i cant help but to perform a linear search over the array. If instead i created an array of size, for instance, Integer.MAXVALUE, to store integers, initialized with zeroes, i could store an integer by placing 1 at its index. Then i could search for its existence in the array in O(1) time. What if i wanted to be able to place multiple units of the same number? No problema, i'd just increase the value stored at the integer's index.

Sorting would be a bit more complicated, but nonetheless lookup and addition could be performed in O(1) time.

# Answer
> 9 votes
The informal definition of an algorithm in a popular textbook goes something like:

An algorithm is (1) a well defined computational procedure (2) that takes some input and (3) produces some output (4) for a well defined computational problem.

In your first case you have coded an algorithm where: The problem is to find the factorial (part 4 of definition), given int n as input (part 2 of definition), the code describes the computation to be performed (part 1 of definition), the output is the factorial (part 3 of definition).

In your second case: The problem is to find the array element at position n (part 4 of definition), given n as input (part 3 of definition), the code describes the computation to be performed (part 2 of definition), the output is the element at position n (part 1 of definition).

You have stored factorials there so it gives you factorials. If you had stored squares or cubes there you'd get squares or cubes, so it cannot be said that the second snippet by itself is an algorithm to compute factorials.

And if you say that an array look up along with an array having f(n) at position n is an algorithm to compute f(n) then you have gone so deep that there is no more computation below. A well defined computational procedure should be a finite piece of information. If an infinite array of factorials is a part of the computational procedure this does not hold. So that wouldn't be an algorithm to compute factorials.

# Answer
> 6 votes
Most broadly, **an algorithm is a series of steps for solving a problem**.

In CS, the following are commonly understood/assumed when using the term algorithm:

* The algorithm has finite description and a well-defined procedure for carrying out its steps given any problem instance. (More below.)
* A problem instance given as a finite string (sequence of input symbols), and the output of the algorithm can be encoded as a finite string.
* A problem is a collection of problem instances together with possible "correct" outputs for each instance. "Solving" means producing a correct output.
* (Usually) the problem instances can be arbitrarily large (there are an infinite number of possible instances that your finite algorithm must solve).

Before CS was founded, mathematicians had the same types of concerns you raise, and introduced formal definitions of computation to address these concerns. Thus, nowadays, we can formalize all of the above assumptions by simply saying **"an algorithm is a procedure that can be implemented on a Turing machine"**. This is probably the best formal answer to your question.

Note that the Church-Turing thesis says that we *think* there is no "more powerful" formalization of algorithms than the Turing Machine.

The factorial example gets into a different model of computation, called non-uniform computation. A Turing Machine is an example of a *uniform* model of computation: It has a single, finite description, and works for inputs of arbitrarily large size. In other words, there exists a TM that solves the problem for all input sizes.

Now, we could instead consider computation as follows: For each input size, there exists a TM (or some other computational device) that solves the problem. This is a very different question. Notice that a single TM cannot store the factorial of every single integer, since the TM has a finite description. However, we can make a TM (or a program in C) that stores the factorials of all numbers below 1000. Then, we can make a program that stores the factorials of all numbers between 1000 and 10000. And so on.

These non-uniform types of computation are typically modeled in theoretical CS by circuits. You consider a different circuit construction for each possible input size.

**Non-uniform models of computation are generally not considered algorithms**, even though they might fit my first sentence. The reason is that they do not fit in our key assumptions: they do not have a finite description that can be implemented to solve the "whole" problem for any input size. Rather, they need a bigger and bigger description as the problem gets bigger (like needing a larger lookup table). However, they are still interesting models of computation.

# Answer
> 5 votes
An algorithm is a program written in C that should work for any length of inputs (assuming infinite memory and unbounded integers). In your examples, if we wanted the program to work for *all* lengths of inputs, then the table in which the results are stored would be infinitely large; programs in C are always finite, so this approach cannot be used.

The definition of algorithm is very resilient: in the early days of recursion theory, many definitions were proposed, and they were all shown to be equivalent. For example, instead of C you can use Turing machines. However, these models are not necessarily equivalent in terms of *efficiency*: a problem could be solved much more efficiently in C than using Turing machines. When interested about efficiency, we should restrict ourselves to all models which are "close enough" to C with respect to running time. For example, if we are allowed to use an instruction which computes $n!$ in one time unit, then the resulting model still defines the same set of computable functions, but some functions (like $n!$) can be computed in it much more efficiently, compared to C.

When worried about actual running times on an actual computer we should be even more careful, but this is usually beyond the limits of theoretical computer science, unfortunately.

---

If we are very fussy, we need to be clear about the difference between *algorithms* and *functions computed by algorithms*. For example, the factorial function gets as input a natural number $n$ and outputs $n!$. The factorial function can be computed by an algorithm. We say that a function is *computable* if it can be computed using some algorithm.

What notion of algorithm should we use? One suggestion, outlined above, is to use C programs. We can call this notion C-computation. Turing-computation is what you get when you use Turing machines. It turns out that a function is C-computable if and only if it is Turing-computable. It is in this sense that both these models of computation are equivalent. Indeed, many other models are equivalent, for example all programming languages in common use (assuming infinite memory and unbounded variables).

We say that a programming language P is *Turing-complete* is a function is P-computable if and only if it is Turing-computable. The Church–Turing hypothesis is an informal statement to the effect that all reasonable computation models *having finite description and taking finite time* are Turing-complete. Your model has a finite description but does not take finite time.

# Answer
> 4 votes
The important part of the common definition of an algorithm that yours is missing is that the specification must be *finite*, and the size of the specification must not vary with the size of the input.

Memory can be arbitrarily large, and so can inputs, but to be a useful definition of an algorithm, the codespace must be finite. Otherwise you get the problem that you just identified.

Unrelated to your question, any realistic definition of an algorithm machine will have memory lookup being at least $O(\log A)$ to fetch memory at address $A$. So your lookup algorithm will at least have time $O(\log n)$ for each bit of the output, which has $O(\log n!)$ bits, so your total runtime of your look up will be $O(n (\log n)^2)$. But if the input is $s$ bits, then $n = O(2^s)$, so your lookup algorithm is $O(2^s~s^2)$, nowhere in the ballpark of $O(1)$.

# Answer
> 3 votes
A few observations that might be helpful:

*Problems* are statements about allowable inputs and corresponding outputs. They're what we want to solve. *Algorithms* are computational procedures. We can say that an algorithm is *correct* with respect to a problem if it accepts inputs which are allowable with respect to the problem and produces outputs according to the problem description.

Both of your examples are algorithms, as they're both clearly computational procedures. Whether the algorithms are *correct* or not depends upon how you define the problem and how you interpret the representation of the algorithm. Some problem statements:

1. Given $n$, compute $n!$
2. Given $n \> 0$ such that $n! \< $ `INT_MAX`, compute $n!$.

Some interpretations of your first code snippet:

1. This is pseudocode which resembles C/C++ except in the details. `int` really means "any integer", for instance.
2. This is to be interpreted as though it were a real C/C++ program.

Interpretation 1 is correct for problem statement 1, as long as the factorial assumes the value 1 for negative numbers (otherwise, we could modify the problem statement to restrict the domain, or the algorithm to account for desired behavior). Interpretation 2 is correct for problem statement 2, with the same caveat.

The second snippet assumes that an `array` has been pre-computed and is accessible to the function. Given this, there are assignments of `array` such that this algorithm would be correct under an "interpret as C/C++" interpretation for the given problem statement: given $n$ such that $n \> 0$ and $n! \< $ `INT_MAX`, compute $n!$. Note that this algorithm has undefined behavior for $n \< 0$ and, as such, it would be unrealistic to hope that the algorithm would be correct for a problem allowing those values.

More generally - pre-computing functions into tables is a common technique for exactly the reason you have noticed: you can perform the computation once, and then reuse the results of that computation over and over. For many functions, it makes a lot of sense. Factorial is a great example: it grows so quickly, a relatively small array can store virtually all integer values you'd need in practice (exercise: what's the smallest integer $n$ such that $n! \geq 2^{32}$? such that $n! \geq 2^{64}$?)

To analyze such *algorithms*, you can used what's called *amortized* analysis. Typically, you use this when some calls to the algorithm might take a long time, while almost all (asymptotically speaking) take less time. In this case, if you want to compute $k$ random factorials (with $k$ much greater than $n$, the typical value for which you're computing the factorial), you'd end up doing work proportional to $kn$ using the first algorithm, but more like $k+n$ using the second. So, you can save some by pre-computing here.

# Answer
> 1 votes
**In a nutshell**: An algorithm is the constructive part of a constructive proof that a given problem has a solution. The motivation for this definition is the Curry-Howard isomorphism between programs and proof, considering that a program has an interest only if it solves a problem, but provably so. This definition allows for more abstraction, and leaves some doors open regarding the kind of domains that may be concerned, for example regarding finiteness properties.

**Warning**. *I am trying to find a proper formal approach to answering the question. I do think it is needed, but it seems that none of the users who replied so far (myself included, and some were more or less explicit about it in other posts) has the right background to properly develop the issues, which are related to constructive mathematics, proof theory, type theory and such results as the Curry-Howard isomorphism between proofs and programs. I am doing my best here, with whatever snippets of knowledge I do (believe to) have, and I am only too aware of the limitations of this answer. I only hope to give some hints of what I think the answer should look like. If you see any point that is clearly wrong formally (provably), please let me now in a comment - or by email.*

## Identifying some issues

A standard way to consider an algorithm is to state that **an algorithm is an arbitrary *finitely specified* program for some computing device**, including those that have no limitations in memory. The langage may as well be the computer machine language. Actually it is enough to consider all programs for a Turing complete computing device (which implies having no memory limitations). It may not give you all algorithms presentations, in the sense that algorithms have to be expressed in a form that is dependent in its details on the interpretation context, even theoretical, as everything is defined up to some encoding. But, since it will compute all there is to be computed, it will include somehow all algoritms, up to encoding.

This definition is hopefully correct, but is it useful? Not really. Given any such computer, which we assume to be a binary computer to simplify the discussion, you can just store an arbitrary finite sequence of bytes in its memory and start executing. You will be computing something. Well, the empty output in many cases. If you are lucky, you will get an infinite enumeration of the decimals of $\pi$, or possibly, as suggested by @hirschhornsalz, *such gems as World of Warcraft, Microsoft Office 17 including Service Pack 6 and Windows 9*. Whatever happens, it will compute something for sometime, possibly stopping right away, or computing for ever with or without output.

The problem is that **one can take any arbitrary bit sequence and see it as an algorithm**, as a program for some computer. But that is perfectly useless when you have no idea what it computes. It might look like the decimals of $\pi$, but contain errors every so often. This is like Borges' Library of Babel, but worse because there is no size limit to the code of algorithms, only that they be finite. The main difference is that Borges' library is finite (since the books have a fixed size), while the number of algorithms is countably infinite. The meaningful algorithms are very few, even the buggy ones, as are the meaningful books in Borges' library. Actually, I would conjecture that, in some way, **Almost all algorithms are uninteresting**, possibly in the mathematical sense of almost all. But that would require more precision in definitions.

So the real question is to know what are the meaningful algorithms. The answer is that the meaningful algorithms are those that solve a problem, computing step by step the "solution", the "answer", to that problem. **An algorithm is interesting if it is associated with a problem that it solves.**

So given a formal problem how do we get an algorithm that solves the problem. Whether explicitly or implicitly, algorithms are associated with the idea that there exist a solution to the problem, which can be proved correct. Whether our proof techniques are accurate is another matter, but we try at least to convince ourselves. If you restrict yourself to constructive mathematics, which is actually what we have to do (and is a very acceptable axiomatic constraint for most of mathematics), the way to prove the existence of a solution is to go through proof steps that actually exhibit a construct that represents the solution, including possibly other steps that establish it correctness.

All programmers think something like: *if I fiddle with the data in such and such a way, then I get this widget which has just the right properties because of Sesame's theorem, and running this foo-preserving transformation I get the desired answer*. But the proof is usually informal, and we do not work out all details, which explains why a satellite tried to orbit Mars underground (among other things). We do much of the reasonning, but we actually keep only the constructive part that builds the solution, and we describe it in a computer language to be the algorithm that solves the problem.

## Interesting algorithms (or programs)

All this was to introduce the following ideas, which are the object of much current research (of which I am not a specialist). The notion of "*interesting algorithm*" used here is mine, introduced as an informal place holder for more accurate definitions.

**An interesting algorithm is the constructive part of a constructive proof that a given problem has a solution**. That means that the proof must actually exhibit the solution rather than simply prove its existence, for example by contradition. For more details see Intuitionistic Logic and Constructivism in Mathematics.

*This is of course a very restrictive definition, that considers only what I called interesting algorithms.* So it ignores almost all of them. But so do all our textbooks on algorithm. They try to teach only some of the interesting ones.

Given all the parameters of the problem (input data), it tells you how to obtain a specified result step by step. A typical example is the resolution of equations (the name *algorithm* is actually derived from the name of a Persian mathematician, Muḥammad ibn Mūsā al-Khwārizmī, who studied the resolution of some equations). Parts of the proof is used to establish that some values computed in the algorithm do have some properties, but these parts need not be kept in the algorithm itself.

Of course, this must take place within a formalized logical framework that establishes what are the data computed with, what are the elementary computational steps that are allowed, and what are the axioms used.

Going back to your factorial example, it may be construed as an algorithm, albeit a trivial one. The normal factorial function corresponds to a proof that, given some arithmetic framework, and given an integer n, there is a number that is the product of the first n integers. This is pretty straightforward, as is the factorial computation. It could be more complex for other functions.

Now, if you decide to tabulate factorial, assuming you can, which is not true for all integers (but could be true for some finite domain of values), all you are doing is including in your axioms the existence of factorial by defining with a new axiom its value for each integer, so that you no longer need to prove (hence to compute) anything.

But a system of axioms is supposed to be finite (or at least finitely defined). And there is an infinity of values for factorial, one per integer. So you are in trouble for your finite system of axioms if you axiomatize an infinite function, i.e. defined on an infinite domain. That translate computationally in the fact that your would-be table look-up cannot be implemented for all integers. That would kill the usual finiteness requirement for algorithms (but is it to be as strict as often presented?).

You could decide to have a finitely defined axiom generator to handle all cases. This would amount, more or less, to including the standard factorial program in your algorithm to initialize the array as needed. That is called memoization by programmers. This is actually the closest you get to the equivalent of a precomputed table. It can be understood has having a precomputed table, except for the fact the the table is actually created in lazy evaluation mode, whenever needed. This discussion would probably need a little bit more formal care.

You may define your primitive operations as you wish (within consistency with your formal system) and assign to them whatever cost you choose when used in an algorithm, so as to do complexity or performance analysis. But, if the concrete systems that actually implement your algorithm (a computer, or a brain for example) cannot respect these cost specifications, your analysis may be intellectually interesting, but is worthless for actual use in the real world.

To consider the last example in the question, it is easy to represent a number on the order of $2^{1000}$ on the computer, and even to sort such numbers. It is somewhat harder (in this universe at least) to implement an array with that size. Hence, it may be an interesting theoretical algorithmic speculation, but it may also not be very applicable in our limited physical world.

## What programs are interesting

This discussion should be more properly linked to results such as the Curry-Howard isomorphism between programs and proof. If any program is actually a proof of something, any program may be construed as an interesting program in the sense of the definition above.

However, to my (limited) understanding, this isomorphism is limited to programs that can be well typed in some appropriate typing system, where types corresponds to propositions of the axiomatic theory. Hence not all program can qualify as interesting programs. My guess is that it is in that sense that an algorithm is supposed to solve a problem.

This probably excludes most "randomly generated" programs.

It is also a somewhat open definition of what is an "interesting algorithm". Anything program that can be seen as interesting is definitely so, as there is an identified type system that makes it interesting. But a program that was not typable so far, could become typeable with a more advanced type sytem, and thus become interesting. More precisely, it always was interesting, but for lack of knowledge of the proper type system, we could not know it.

However, it is known that not all programs are typeable, since it is known that some lambda expression, such as implementing the Y combinator, cannot be typed in a sound type system.

This view only applies to programming formalisms that can be directly associated to some axiomatic proof system. I do not know how it can be extended to low level computational formalisms such as the Turing Machine. However, since algorithmics and computability is often a game of encoding of problems and solutions (think of arithmetics encoded in lambda calculus), one can consider that any formally defined computation that can be shown as being an encoding of an algorithm is also an algorithm. Such encodings probably use only a very small part of what can be expressed in a low level formalism, such as Turing Machines.

One interest of this approach is that it gives a notion of algorithm that is more abstract and independent of issues of actual encoding, of "physical representability" of the computation domain. So one can, for example, consider domains with infinite objects as long as there is a computationally sound way of using them.

# Answer
> 1 votes
An *algorithm* is a program written in a Turing-complete language that provably halts on all valid inputs. All standard programming languages are Turing-complete. The word originates as a European translation of the name al-Khwārizmī, a Persian mathematician, astronomer and geographer, whose work built upon that of the 7th-century Indian mathematician Brahmagupta, who introduced the Indian numeral system to the western world.

The question seems to be basically about whether lookup tables are parts of algorithms. Absolutely! In Turing machines (TM) tables can be encoded in the state table of the TM. The TM can initialize the tape based on a *finite* amount of data stored in the transition table. However, "algorithms" that don't run on infinite inputs, only finite inputs, are "trivially" finite-state machines (FSM).

# Answer
> 0 votes
There is no good formal definition of "algorithm" at the time of writing. However, there are smart people working on it.

What we know is that whatever an "algorithm" is, it sits somewhere between "mathematical function" and "computer program".

A mathematical function is formal notion of a mapping from inputs to outputs. So, for example, "sort" is a mapping between a sequence of orderable items and a sequence of orderable items of the same type, which maps each sequence to its ordered sequence. This function could be implemented using different algorithms (e.g. merge sort, heap sort). Each algorithm, in turn, could be implemented using different programs (even given the same programming language).

So the best handle that we have on what an "algorithm" is, is that it's some kind of equivalence class on programs, where two programs are equivalent if they do "essentially the same thing". Any two programs which implement the same algorithm must compute the same function, but the converse is not true.

Similarly, there is an equivalence class between algorithms, where two algorithms are equivalent if they compute the same mathematical function.

The hard part in all this is trying to capture what we mean by "essentially the same thing".

There are some obvious things that we should include. For example, two programs are essentially the same if they differ only by variable renamings. Most models of programming languages have native notions of "equivalence" (e.g. beta reduction and eta conversion in lambda calculus), so we should throw those in too.

Whatever equivalence relation we pick, this gives us some structure. Algorithms form a category by virtue of the fact that they are the quotient category of programs. Some interesting equivalent relations are known to give rise to interesting categorical structures; for example, the category of primitive recursive algorithms is a universal object in the category of categories. Whenever you see interesting structure like that, you know that this line of enquiry will probably be useful.

# Answer
> -4 votes
Your question and description do not relate that much. Algorithm is theoretical and doesnt relate to any programming language. Algorithm is a set of rules or steps (procedure) to solve a problem. Your problem can be solved in many ways or many algorithms.

Your second solutions means to compute first a big array of factorials which initially will take a lot of time then store it. It will consume more storage but eventually it will be faster while the first one doesnt consume storage but consumes computing power so you will have to chose depending on your environment.

---
Tags: algorithms
---


# Question
Title: Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad?
I am doing an exercise from a Big Data course I'm taking on Coursera (this exercise is for experimenting with a big-data problem and is not for any credit or homework) , the assignment was described briefly:

> Your task is to quickly find the number of pairs of sentences that are at the word-level edit distance at most 1. Two sentences S1 and S2 they are at edit distance 1 if S1 can be transformed to S2 by: adding, removing or substituting a single word.

I am then given a large txt file that contains about $10^6$ sentences.

The way I tried to attack this problem:

Observation $1$: If the length of two sentences is greater then $1$ then they are not at an edit distance $1$.

Observation $2$: Let $A\_1,...,A\_5$ be five consecutive words from a sentences and let $B\_1,...,B\_5$ be another five consecutive words chosen from different indexes (that is if we label the words of a sentence then $B\_i$ and $A\_j$ does not share an index.

* Five is a small arbitrary number I chose

I used something like a curried syntax to get a hashtable that keeps a 3-touple: $(X,Y,Z)$

Where I mapped each sentence as follows:

* $X$ is the number of words the sentence have.
* $Y$ is obtained by a hash function on the content of the words (I will soon describe this hash function)
* $Z$ is a list of integers containing the index of the line in the document \[the line number\] that was mapped to $(X,Y)$

In C# this corresponds to an object of a type

Dictionary\< int, Dictionary\< int, List\< int\>\>\>

So I kept two Hashtables of the above form, where I took the first five words to hash and get $Y$ and words $6-10$ to hash and get another value of $Y$.

Then given a sentence - compute the two $Y$ values it would of gotten and look at buckets with length that differs at at most $1$ from this sentence length and share one $Y$ value this sentence.

Let me describe the hashing function I used to get $Y$ -

1. I took the $A\_i$ (similarly with the $B\_i$) and concatenated them
2. I looked at this string as a byte array (that is by the bits that takes to represent the numbers) I then applied a the SHA-1 hash function on it (there are no security reasons for this but I wanted something that hashes well)
3. I took the last $4$ bytes in the SHA-1 hash and I looked at it as a positive integer (by looking at the last $32$ bits and considering it as an integer then applying the absolute value function). Call this result $R$

4. $Y= R\\%p^{2}$

where $p$ was chosen as follows: I counted how many lines of a given length $l$ appear (say $n\_l$), for lines of length $l$ I chose $p$ s.t $$\frac{n\_l}{p^2}\leq 3$$

the following is a Histogram showing $n\_l$ as a function of $l$

which should give some indication of the values chosen for $p$.

However - There are too many collisions - I get about $6$ elements in each bucket.

I took one example of such a bucket and I printed those sentences (I hoped they are similar so they would have a good reason to be mapped to the same bucket) by they are very different from one another. This is a printscreen of those sentences printed to the console.

**Question**: Why do I get a large number of collisions ?($6$ in average on $10^5$ buckets I considered where if I had even distribution I would expect $3$ from the choice of $p$, some buckets have a few tens of elements in them)

Could the problem be that I used modulo a square of a prime and not a prime ? is it that significant?

# Answer
> 1 votes
There are a lot of things which could have gone wrong, but it is really hard to say, especially since you don't tell us the bad values of $n\_l$ and $p^2$. So for now, here are some comments:

1. SHA1 is slow relative to non-cryptographic hashes. If you are lucky then your programming language already has a fast hash implementation.
2. There is no need to take the absolute value of the last 32 bits. Instead, consider it as an unsigned integer (unless you're using a language such as Java which doesn't have them).
3. Since the last 32 bits of the SHA1 hash are very random, you can take them modulo any modulus that you want (assuming it is small compared to $2^{32}$). There is no particular advantage in choosing a prime or a prime power.
4. Due to the random nature of the hash, you don't expect sentence snippets falling into the same bucket to have anything in common, unless they're *exactly* equal.
5. If everything is random and $n\_l/p^2$ is very small compared to $n\_l$ then you expect the distribution of balls in each bucket to be roughly Poisson with expectation $n\_l/p^2$. Assuming this, for $n\_l/p^2 = 3$, the probably to get at least 6 balls in some bucket is roughly $0.084$, so you would expect this fraction of buckets to contain at least 6 balls. Assuming a maximum value of roughly $100,000$ buckets (my estimate from your graph), you expect to see 7 buckets having at least 12 balls. You shouldn't be getting buckets with a few tens of elements, though: the probability of having any bucket with at least 20 balls is at most $8 \cdot 10^{-6}$, for example.

In view of this, I suggest you pick some particular experiment and compare the distribution of the number of balls in buckets to the corresponding Poisson distribution. If you find any major discrepancy (an ill-defined concept), let us know the exact values of $n\_l$ and $p^2$ you used.

# Answer
> 1 votes
There are some reason why people would like to use modulo prime hashing. Assume we need a hash from $\\{1,\ldots,n\\}$ to $\\{1,\ldots,m\\}$, one popular choice is $h(n) = (an+b)\mod p\mod m$, where $p$ is a prime greater than $n$ and $a,b$ are randomly chosen from $\\{1,\ldots,p\\}$. Hashing function $h$ has a advantage that $h(x)$ is almost uniform and $h(i),h(j)$ are almost independent. Such property is called 2-universal, which is very useful. This is why you may have seen $h$ in the textbook.

While 2-universal, and other ideal properties of hashing, is useful only if you are fighting against malevolent input. On the opposite, when the input is random, any function that maps equal number of keys to different bucket is equivalent good. You do not need those heavy hash e.g. SHA1. You should use some lightweight hash functions, while I'd recommend you to use more buckets, e.g. $2^{32}$, to avoid collision. C# would take care of the space, you dont need to mind it.

Finally, when people use hashing, they typically use it to speed up accession. While in your homework, hashing can be used more **constructively**. There exists some hash function $h\_1,h\_2$, which can be computed in linear time, such that the collisions between $h\_{\*}(s\_i), h\_{\*}(s\_j)$ hints $s\_i,s\_j$ has word-level edit distance at most 1.

---
Tags: hash, big-data
---


# Question
Title: What is the significance of the following equation in computer vision?
Say I have a set of sample measurements of a one dimensional curve in the image plane $f(x)$. What is the purpose of minimizing the following functional $$E(S) = \int \left\[\lambda(S''(x))^2 + (f(x) - S(x))^2 \sum\_k \delta (x - x\_k)\right\]dx$$

I believe it has something to do with energy minimization and snakes.

# Answer
I would agree - energy minimization for snakes (active contours).

It minimizes second derivative - bending of the curve.

Minimizes the difference between the image (probably it's edges) and contour (at discreet contour points - the reason for having Dirac impulse in the expression).

Usually one could expect also to have minimization of the first derivative - stretching of the snake.

More details and references on wiki - active contour
> 1 votes

---
Tags: computer-vision, mathematical-foundations
---


# Question
Title: Intersections of some context-free languages
Suppose We have Some language as follows:

$L\_1=\\{w^\* | w=x \text{ and } x \in \Sigma^\*\\}$

$L\_2=\\{ww^R ww^R | w \in ( \Sigma + \Sigma)^\*\\}$

$L\_3=\\{w | w=xy, x,y \in \Sigma^\*, y \text{ is a substring of } x\\}$

1) there is a PDA (push down automata) that accept $L\_2 \cap L\_3$

2) there is a PDA (push down automata) that accept $L\_2 \cup L\_3$

3) there is a PDA (push down automata) that accept $L\_1 \cap L\_3$

4) there is a PDA (push down automata) that accept $L\_1 \cup L\_2$

I read in some sites that:

(a) is false, and we can say 3 and 4 are wrong because we have no language that is not closed under union but closed under intersection.

I read a lot of material for finding the answer of this question mentioned by Prof. M. Farshchi on Entrance Exam in 2012, but I failed. I need some one to help me with a bit detail for each one. Thanks.

# Answer
Notice that $L\_3 = \Sigma^\*$, since you can always choose $y=\epsilon$ (the empty string is a substring of any string) and then choose $x$ from $\Sigma^\*$. $L\_1$ is also $\Sigma^\*$, since $L$ is always a subset of $L^\*$ and we're basically saying $L\_1 = (\Sigma^\*)^\*$. These observations imply the following: the answers to #2, #3 and #4 are "yes" (indeed, there's a DFA with one state accepting each of these, which are all $\Sigma^\*$)... and the intersection in #1 is simply $L\_2$, so the question is really "is $L\_2$ context-free?"

Please also note that we have other questions on the site about proving and disproving that languages are context-free.

To clarify:

1. $L\_2 \cap L\_3 = L\_2 \cap \Sigma^\* = L\_2$
2. $L\_2 \cup L\_3 = L\_2 \cup \Sigma^\* = \Sigma^\*$
3. $L\_1 \cap L\_3 = \Sigma^\* \cap \Sigma^\* = \Sigma^\*$
4. $L\_1 \cup L\_2 = \Sigma^\* \cup L\_2 = \Sigma^\*$

As for $L\_2$:

First note that I'm assuming $(\Sigma + \Sigma)^\*$ is a funny way of writing $\Sigma^\*$. Plus usually stands in for union when dealing with regular expressions, and I'm guessing that's the intention here as well, though it would be well to confirm this.

Assume $L\_2$ were context free. By the pumping lemma for context-free languages, we could write any word $w \in L\_2$ of length at least $p$ as $uvxyz$ where $|vxy| \leq p$, $|vy| \> 0$ such that $uv^kxy^kz \in L$ for all $k \geq 0$. Consider the word $(0^p1^p)(1^p0^p)(0^p1^p)(1^p0^p)\in L\_2$ (parentheses added for clarity). We consider cases for the assignment of $vxy$:

1. $vxy$ consists entirely of $0$s from the first (parenthesized) part of the string. Pumping will change the number of $0$s without changing the number of $1$s in the first part, leading to a string that can't possibly be in the language.
2. $vxy$ consists of a mix of $0$s and $1$s from the first (parenthesized) part of the string. Pumping will change the numbers of $0$s and $1$s in the first part without affecting the other parts, leading to a string that cannot be in the language.
3. $vxy$ consists of a $1$s from the first (parenthesized) part only. See argument in point 1 above.
4. $vxy$ consists of $1$s from the first part and $0$s from the second. See arguments above.

etc. There are 15 cases in total, but the arguments are all basically the same: you always get some parts out of sync (the $p$s won't match). This means that the language is not context-free.
> 2 votes

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


# Question
Title: Hamming distance required for error detection and correction
I have already asked a pair of questions on the hamming distance, hamming code, valid and invalid codewords on this website, because I cannot understand those concepts fully, and in a few weeks or less, I am going to have an exam also on those topics, I really do not understand. I have tried to take a look to wikipedia articles, but it is, for me, quite complicated to understand.

My question this time is more concrete. I have a figure, representing how many errors can we **detect** and **correct** according to the `hamming distance`. The thing I am not understanding is why, for example, with an hamming distance of 3, we can just detect 2 bit flips and correct 1 bit flip. I know there are 2 formulas (that you can see in the picture), which bring us to that result, but I would like understand why those formulas are correct. Why, with an hamming distance of 3, we can just detect 2 errors and correct 1.

This is picture:

# Answer
The Hamming distance being 3 means that any two code words must differ in at least three bits. Suppose that 10111 and 10000 are codewords and you receive 10110. If you assume that only one bit has been corrupted, you conclude that the word you received must have been a corruption of 10111: hence, you can correct a one-bit error. However, if you assume that one or two bits could have been corrupted, you don't know if 10110 should be 10111 (one 1 got turned into a 0) or 10000 (two 0s got turned into 1s). You can correct one-bit errors (if you assume that those are the only kind that occur) but **you can't tell the difference between a one-bit error from one codeword and a two-bit error from another**, so you can't deal with two-bit errors at all. If a two-bit error occurs, you'll detect that *some* error occurred, but you'll assume it was a one-bit error from a different codeword and "correct" it wrongly.

In contrast, with the distance-4 code illustrated in the fourth diagram, you can detect two-bit errors. If you receive the word in the middle, you can tell that (at least) two bits got corrupted but you can't tell whether you were supposed to see the blue codeword on the left or the one on the right.
> 11 votes

---
Tags: coding-theory, error-correcting-codes
---


title: Passing parameters to threads

text:
# Question
Title: Passing parameters to threads
in Programming language course my professor take an example.

Suppose the following code:

```
int x=initialization();
Thread T1=new computethread(x);
Thread t2=new evaluatethread(x);
...
...
Thread t100=new evaluatethread(x);

```

threads `t1` to `t100` needs the initial value of variable `x` for their computation and `t1` need to change the `x`, which transfer of parameter for `computethread`, `evaluatethread` is preferred?

my professor say:

```
1) call by value result

2) call by ref

```

is preferred for sending x to `computethread`, `evaluatethread`, why call by result or call by name or this order like 2) call by value result, 1) call by ref is not preferred? why he conclude these are better?

# Answer
Call by reference is cheaper than call by value since you don't need to copy your object. That's why we prefer it when possible. If the thread needs to change its local copy, then you need it to have a copy of its own, which is the same as call by value.
> 1 votes

---
Tags: compilers, threads
---


# Question
Title: If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?
The reverse, $w^{R}$, of a string $w = w\_1w\_2...w\_n$ is the string $w\_n...w\_2w\_1$. Suppose that L is a regular language. Must the language $L\_1 = \\{w : w^Rw \in L\\}$ be regular, or may it be non-regular? Explain.

Intuitively, I suspect that $L\_1$ may be nonregular, since the set of even-length palindromes of an arbitrary regular language $L$ isn't necessarily regular. However, I'm not sure that the pumping lemma can be used to prove the non-regularity of $L\_1$.

# Answer
> 2 votes
Here is sdcvvc's answer in plain language. Suppose we are given a DFA for $L$ with set of states $S$, starting state $s\_0$, accepting states $F$, and transition function $q$. We construct an NFA for $L\_1$ as follows. The NFA maintains two states $(s\_1,s\_2) \in S^2$. Its initial states are $(s,s)$ for all $s \in S$, and its accepting states are $(s\_0,f)$ for all $f \in F$. At state $(s\_1,s\_2)$, upon reading a symbol $a$, the NFA can move to any state $(t\_1,t\_2)$ such that $q(t\_1,a) = s\_1$ and $q(s\_2,a) = t\_2$. This completes the description of the NFA.

This NFA is trying to "prove" that $w^Rw$ is in $L$. The idea is that after reading a prefix $x$ of $y$, say $w = xy$ and so $w^Rw = y^Rx^Rxy$, the NFA will be in state $(q(s\_0,y^R),q(s\_0,y^Rx^Rx))$. At the beginning, that is when $x = \emptyset$, both states are the same $q(s\_0,w^R)$, which the NFA guesses. This explains our initial states. Upon reading a character $a$ while at state $(s\_1,s\_2)$, the second part of the new state is $t\_2 = q(s\_2,a)$, while the first part is some $t\_1$ satisfying $q(t\_1,a) = s\_1$. Finally, when we have finished reading the word, that is when $y = \emptyset$, we should be at the state $(s\_0,q(s\_0,w^Rw)) \in \\{s\_0\\} \times F$, since $w^Rw \in L$. This explains our choice of accepting states.

# Answer
> 2 votes
It will be regular.

> Let $M$ be the syntactic monoid of $L$ and consider the monoid $M^{\operatorname{op}} \times M$ (where $M^{\operatorname{op}}$ is $M$ with multiplication flipped).

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


# Question
Title: top k selection in fixed size priority queue with dynamically changing values
My question is something of a scheduling problem. I'd like to know what algorithm to use to find the top k items in a fixed length queue in which the values of the items change dynamically.basically a long running online top k selection

I imagine that operating systems do this all the time, but not being a systems guy, I don't know what terms to search for. Thanks in advance.

# Answer
> 0 votes
The problem is known as partial sorting. Wikipedia gives various algorithms, using heaps and so on.

---
Tags: scheduling
---


# Question
Title: Find the max of a convex function in fewest samples
Suppose there is a convex function, and a certain domain interval. I want to find the max of this function within the interval. The goal is to minimize the number of times the function is evaluated, because evaluating it is expensive.

I can think of a naive solution involving evaluating the function at two points of the interval (thereby partitioning the interval into three sub-intervals) and discarding the edge sub-interval of the point with the lower function value. But, I am not sure whether it's optimal.

# Answer
> 0 votes
As the function $f$ is convex, its maximum value in interval $\[a,b\]$ is either $f(a)$ or $f(b)$. Otherwise, it will violate Jensen's inequality.

---
Tags: algorithms
---


# Question
Title: What is the difference between shortest distance and shortest path?
I am studying graph currently. I found a question, which asks for

1. The List `A[]` which shows shortest distances between $V$ and every other vertex
2. The List `B[]` which shows shortest paths between $V$ and every other vertex

as subpoints. I don't think the question wants me to compute the same values twice, but I don't know what the difference between shortest distance and shortest path is. Can anyody explain?

# Answer
As @randomA already indicated in a comment, a shortest path from $v$ to $w$ is a sequence of vertices (that describes a path from $v$ to $w$, which is shortest among such sequences).
The shortest distance on the other hand is the length of a shortest path, i.e. a number.

As a sidenote, be aware that there can be multiple shortest paths (but only one shortest distance). Thus, you might want to check, if the the question requires you to find one or all of them.
> 2 votes

---
Tags: terminology, graphs
---


title: Positional number representation

text:
# Question
Title: Positional number representation
There is a definition of integer representation:

> A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position. (Adapted from the American National Dictionary for Information Processing Systems.)

It is not clear to me. Could you give an example reflects that definition? In general, I don't understand what is the `successive integral power of 2` and what is the `succesive bits`?

# Answer
This appears to be nothing more than a description of the standard binary notation. List the bits in the string and below them, starting with 1 at the rightmost position and multiplying by 2 at each position to the left: $$\begin{array}{lccccc} \mathbf{bits:} & 1 & 1 & 0 & 1 & 0\\ \mathbf{powers\ of\ 2:} & 16 & 8 & 4 & 2 & 1\\ \mathbf{product:} & 16 & 8 & 0 & 2 & 0 \end{array}$$ then add the resulting products: $16 + 8 + 0 + 2 + 0=26$, as it should be, since $\mathtt{11010}\_2=26$.

The `successive integral powers of 2` are just those that appear in the second line, right to left, and similarly `successive bits` are those in the first line, again reading from right to left. I must confess to being confused by the phrase `except perhaps for the bit in highest position`.
> 2 votes

---
Tags: number-formats
---


# Question
Title: Can there exist a recurrence relation for "sequential search"?
I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.

# Answer
Sure.

The cost of searching a list of length zero is zero; the worst-case cost of searching a list of length $n$ is one greater than the cost of searching a list of length $n-1$. So $$\begin{align\*}T(0)&=0 \\ T(n)&=T(n-1)+1\\,,\end{align\*}$$ with solution being, as you'd expect, $T(n)=n$.
> 3 votes

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Compute the Hamming code with odd parity for the memory word 1101 1001 0001 1011
This is the problem I have:

> Compute the Hamming code with odd parity for the memory word 1101 1001 0001 1011 (2 pts.). In your solution, mark the parity bits as in the following example, where parity bits are: 3, 5, 11, and 13

```
0001 0100 1011 1100 1001 1
  P  P      P  P

```

> Note: This is only an example on how you should mark the parity bits. It is not a correct code word by any means.

There are 2 things I do not understand:

1. A 16-bit memory word needs 5 check bits from this formula $2^k -1 \ge m + r$, where `m` is the number of data bits and `r` the number of check bits. But in the exercise we have just 4 check positions.
2. The check positions usually occupy the positions that are power of 2, for example $2^0$, $2^1$, $2^2$... So why are they asking to use other positions for the check bits?

# Answer
> 1 votes
1. They clearly say that the example is only given as an example. If you believe you need 5 parity bits - use 5 bits. They use 4 bits in their example for no good reason.
2. True, they still wish you to mark it clearly. I guess the reason is (a) to make sure *you* know that the parity comes in powers of 2, and (b) to ease their grading. note you **should not** use positions 3,5,11, and 13! these are again only their example, and the note below the example clarifies you need not pay attention to it.

(at least, that's the way that **I** understand the question. There is a small ambiguity there that allows one to understand it the way you did)

---
Tags: memory-hardware, coding-theory, hamming-code
---


# Question
Title: How do I know if my algorithm is right (without coding)?
For some background : I think I am quite good at advanced (graduate/research level) mathematics and physics but I have no CS background. Now I am taking a graduate level class on algorithms.

I don't think I have ever written a wrong proof in mathematics - as in either I can prove something or I can't. I have never faced a situation whereby I wrote a wrong proof - its just obvious if I am writing a wrong proof.

BUT with algorithms it seems that its just trivial to write a wrong algorithm. I am simply not getting as to how does one know if what one has written is right or wrong. There seems to be something "mysterious" going on here - like while I write a recursive/dynamic programming solution etc. - I am thinking that I wrote something right but then somebody comes along with an example where my answer doesn't work!

Its quite contrary to my years of experience of writing proofs in mathematics!

This is getting freaking scary! Its better to not be able to do something than to be writing a wrong answer and not knowing it! (...often enough I land up writing a greedy solution trying to optimize something locally but its not the globally correct answer!..how does one see it!?...coming up with a counter-example is also almost always very hard!..)

Can someone help?

---

I am currently doing a lot of practice with this but I wonder if there is something that I am missing totally!

# Answer
You prove that the algorithm is correct. This requires (1) writing out a precise specification of what you mean by correctness, (2) writing a mathematical proof that your algorithm meets this specification. Algorithms courses and textbooks often include some material on how to prove algorithms correct, as well as many examples of this, so that would be a good starting point to study, if you want to learn more about proofs of correctness for algorithms. See also formal methods / formal verification, and possibly the following question on this site: How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
> 3 votes

# Answer
That's a great question, and the answer has **nothing** to do with coding. The answer is simple: in order to prove that an algorithm is correct, you will have to... hmmm... prove it!

An algorithm, in many senses is an abstract mathematical creature, which you can mathematically verify under certain assumption and conditions. Maybe the confusing part is that Algorithm can be CODED into a program, but this is only an instantiation of the algorithm, not the algorithm itself. It might be easier to keep the algorithm as a "pseudo code" to be able to define its supposed action, without the disguising details of the specific programing language you use. That way it is easier to believe that an algorithm is indeed a mathematical object (which is run on a mathematical abstraction of a computing device, e.g. on a Turing machine).

Given an algorithm $\textsf{ALG}$ that is supposed to do $X$, you can consider the (mathematical!) theorem "$\textsf{ALG}$ does X" and then try to prove it. To be concrete: assume you write a sorting algorithm $\textsf{SORT}$, then to prove it correct you want to prove the theorem "on input any list of $n$ numbers, $\textsf{SORT}$ outputs a lexicographical ordering of the input"

The details of proving such a theorem vary according to your algorithm and the problem you wish to solve. It's too broad to discuss in this thread.

However, to get some intuition, I would recommend you to look at graph-theory and algorithms for graph-theory. There are many nice algorithms for various graph-related tasks (e.g., performing a BFS search, doing a DFS search, finding a spanning tree, etc) and you will be able to find detailed proofs that those algorithms actually work they way that should (e.g., that BFS covers *all* the nodes and in the right order; that the spanning tree is indeed a spanning tree, etc.). Since the field of graph-theory is very close to mathematics, these examples might help you to "bridge" you prior knowledge and apply it onto computer-science questions.
> 1 votes

---
Tags: algorithms, education
---


# Question
Title: Estimate the running time of counting nodes in a binary tree
I am asked to write an efficient method that computes the number of nodes in T, and here is what I did:

```
public int numOfNodes(Node t)
{
    if (t==null)
        return 0;

    return numOfNodes(t.left) + numOfNodes(t.right)+1;
}

```

Every node needs invokes two recursive calls, so the running time is $O(2^N)$.

Is my estimation of the running time correct? It seems to be too slow.

# Answer
> 1 votes
**Hint 1.** You say the running time is $O(2^N)$ but what is $N$? $2^N$ would indeed be bad if $N$ were the number of nodes.

**Hint 2.** How many times does your code visit each node in the tree? How much time does it spend on each node?

---
Tags: binary-trees
---


# Question
Title: Optimal path through a DAG with sparsely available edge weights
I would like to create a plot of certain metrics that are collected at revisions of a software system. The objective of the software engineers is to minimize those metrics.

For version control, the engineers are using Git, so there is a DAG of commits (revisions). However, the metrics are only available for a *subset* of those commits. It is not feasible to collect metrics for all of the commits.

What path finding algorithm would yield the most relevant data to plot a "downward trend" in the metrics that is **minimally erratic**, resolving **ties** in favor of the path with **maximum detail**?

# Definitions

**erraticism**: The sum of the absolute differences between the metric at each pair of adjacent commits along the path. Example: For path `A-B-C` where `A=10`, `B=7`, `C=5`, the erraticism is `(10 - 7) + (7 - 5) = 3 + 2 = 5`.

**detail**: The quantity of commits that have known metrics along a path. Example: for path `D-E-F` where the metric at `D` and `F` is known, but `E` is unknown, the detail is `2`.

# Scenarios to illustrate objective function

## Metrics available for all paths

Say that `D` is the most recent commit. `D` has two parents, `B` and `C`. `B` and `C` share a single parent `A`.

```
  10 -> A
       / \
11 -> B   C <- 7
       \ /
   5 -> D

```

In this scenario, all four commits have metrics available. In this case, the least "erratic" path is preferred.

If `A=10`, `B=11`, `C=7`, and `D=5`, the path `A-C-D` is preferred.

## Metrics available for only one competing path

If the metric is unavailable for commit `C`, then the path `A-B-D` is preferred.

```
  10 -> A
       / \
11 -> B   C <- unknown
       \ /
   5 -> D

```

## Metrics available for no competing paths

If the metrics are only known for commits `A` and `D`, then it doesn't matter whether we traverse through commit `B` or commit `C`, because neither commit will be displayed on the plot. The plot will display path `A-D`.

```
       10 -> A
            / \
unknown -> B   C <- unknown
            \ /
        5 -> D

```

## Competing paths of various lengths

### Maximum detail

This is where it gets complicated.

Generally it is preferable to have more detail in the plot. So in the following example, path `A-C-E-F` is preferred:

```
       10 -> A
            / \
      7 -> B   C <- 8
           |   |
unknown -> D   E <- 6
            \ /
        5 -> F

```

Path `A-B-D-F` has `erraticism=5`, `detail=3`. Path `A-C-E-F` has `erraticism=5`, `detail=4`. Detail breaks the tie, and path `A-C-E-F` is selected.

### Minimally erratic

However, we do not prefer the path with greater detail when that path is more erratic than the alternative. In this case, path `A-B-F` is preferred:

```
       10 -> A
            / \
      7 -> B   C <- 11
           |   |
unknown -> D   E <- 6
            \ /
        5 -> F

```

Path `A-B-D-F` has `erraticism=5`, `detail=3`. Path `A-C-E-F` has `erraticism=7`, `detail=4`. Path `A-B-D-F` is selected.

# Answer
> 1 votes
Your question is not self-consistent, so you first need to figure out exactly what you are looking for, before we can identify an algorithm to find it.

However, once you figure that out, it is likely that dynamic programming will solve your problem. Dynamic programming is powerful and likely to solve your problem for any reasonable criterion that depends only on detail and erraticism (assuming it is monotonic in each variable separately).

In particular, define $f(v,d)$ as follows:

> $f(v,d) = $ the smallest possible erraticism that can be achieved by a path from $A$ to $v$ whose detail is $d$.

In other words,

$$f(v,d) = \min \\{\text{erraticism}(p) : p \text{ is a path from $A$ to $v$ and } \text{detail}(p)=d\\}.$$

Let $\text{pred}(v)$ denote the set of vertices $u$ such that there is a path from $u$ to $v$ where you have the metric for $u$ but not for any other intermediate vertex in the path (i.e., not for any other vertex in the path other than $u$ or $v$).

Notice you can compute $f(v,d)$ given the values of $f(u,c)$ for all $u \in \text{pred}(v)$ and all integers $c$ satisfying $0 \le c \le d$. Call this "formula (\*)".

Since the graph is guaranteed to be a dag, you can linearize it (topologically sort it). Then, visit the vertices in topologically sorted order. When you visit $v$, compute $f(v,d)$ for each possible $d$ using formula (\*) -- this is possible because the topological sort ensures you will have computed $f(u,c)$ before visiting $v$.

There are $|V|$ possible vertices and at most $|V|$ possible values for the detail. Calculating $f(v,d)$ can be done in $O(|V|)$ time, since the set $\text{pred}(v)$ has size at most $|V|$. Therefore, the running time of this will be at most $O(|V|^3)$.

In practice, I expect the algorithm will be faster than that. For instance, you only need to compute $f(v,d)$ for $d=0,1,2,\dots,\ell$, where $\ell$ is the length of the shortest path from $A$ to $v$. Also, for most vertices, the size of $\text{pred}(v)$ will usually be much less than $|V|$ -- maybe more like $O(1)$.

Once you have computed $f(Z,0),f(Z,1),f(Z,2),\dots$, where $Z$ is the final node, then you can use all of that information to select which path you want. For instance, if your criterion is "minimize erraticism, and break ties in favor of greater detail", you just compute $\min \\{f(Z,d) : d=0,1,2,\dots\\}$, resolving ties in favor of the larger $d$. As another example, if you want to modify that criterion by ignoring all paths with detail 0, just ignore $f(Z,0)$. Or, if you want to ignore all paths with detail 0 if there exists any path with detail $\> 0$, then check whether any of $f(Z,1),f(Z,2),\dots$ are finite ($\< +\infty$); if yes, then you ignore $f(Z,0)$. And so on. Hopefully you can see how to adapt the dynamic programming solution to handle many possible variations for the objective function.

For specific objective functions, there might well be even more efficient solutions -- but since it is not clear from your question at the time of writing just what objective function you want to minimize, I thought I would outline a general answer that works for a large class of possible objective functions.

---
Tags: shortest-path
---


# Question
Title: Difference between equivalence and implication
In terms of CTL formulae, what is the difference between equivalence and implication?

(prop = some proposition, && = conjunction, AG = CTL syntax for "globally holds")

E.g. AG (prop1 && prop2) versus (AG prop1) && (AG prop2)

Are those two formulae related by implication i.e. the left hand side implies the right hand side? Or are they actually equivalent?

# Answer
First, to answer the question in your question title: the difference between equivalence and implication in CTL formulae is the same as the difference between equivalence and implication in propositional logic, that is, $A \leftrightarrow B$ is the same $(A \to B) \land (B \to A)$.

But your real question is whether $\mathrm{AG}\\,(A \land B)$ is equivalent to $\mathrm{AG} \\,A \land \mathrm{AG}\\,B$. To solve this question, you have to look at the semantics of the operators AG and $\land$; that is, what do $\mathrm{AG}\\,\phi$ and $\psi\_1\land\psi\_2$ mean (for arbitrary formulas $\phi,\psi\_1,\psi\_2$?

The semantics of CTL works via transition systems. Two formula are equivalent if they are true in exactly the same transition systems and states. Looking at the semantics of AG and $\land$, it should be fairly easy to decide whether there is a transition system where the one formula is true and the other isn't.
> 3 votes

---
Tags: logic, model-checking, temporal-logic, computation-tree-logic
---


# Question
Title: Detecting palindromes in binary numbers using a finite state machine
In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary sequences (no points if we do, it's just a food for thought).

I specifically asked the professor, knowing a little about CS and that palindromes aren't regular, and that a finite state machine can only detect a regular language. But his answer surprised me, since he said that it is indeed possible and that he thinks we should be able to come up with a sotluion.

This brings two questions:

1. Maybe the binary sequence is a special type of palindrome that is regular? (I'm a little fuzzy on this)
2. Or the technique we're using to represent the state machine is more powerful than I think.

In case it's 2), I'll try to explain how we're representing the problem.

Imagine a finite wall, which is supposed to be filled with a predefined types of tiles. Each tile has four colors

You can design any tile you want, and as many as you want, but there has to be a finite number of tiles. They can be arranged in a single row, or into multiple rows, but the topmost row has to always match against the `0` and `1` colors. The end colors of the wall also have to be defined ahead of time, and the tiles have to match those, and they also have to match the adjacent tiles.

Here's an example of a pattern that detects a sequence of `01010101...01`

The question is, is this pattern more than just modeling a finite state machine? If not, how can I use this to detect palindromes?

**Update: There has to be a finite number of tile designs, and the number of tiles has to be finite as well (the input will always be finite as well). As for the rows, there can be an arbitrary number of rows, the only condition is that the tiles on a second row must match in the top color with the tiles on the row above them. The number of colors isn't limited as well, though it can't be infinite.**

# Answer
> 5 votes
**In a nutshell**: *As presented, with a single row of tiles, the tiling system is equivalent to a finite state automaton. It cannot recognize the set of palindromes which is context-free, but not regular. However, if the tiling system is extended, allowing as many rows as needed (possibly with the addition of a column on each side), then it becomes as powerful as a linear bounded automaton, recognizing context-sensitive languages, and thus also palindromes. The last section is a simple set of tiles to recognize palindromes.*

## Recognizing palindromes with a single row of tiles

Regarding your tiling system, I am missing some details. Is the number of tiles finite, or just the number of different tile designs. More precisely, while the number of designs can be finite, i.e. the same for all sequences to be recognized, the number of tiles of each design should be sufficient in number, which may depend on the sequence to be recognized, though each recognition would use only a finite number of tiles.

If the number of tile is finite, less than some fixed number $n$ that is independent of the sequence to be recognized, you can at best recognize finite sets of sequences, which is much less than all regular languages.

Second point: is the number of different colors can be set at any value, the same for all sequences of the language to be recognized. If not you cannot recognize all regular languages.

If you have any number of tiles, finite number of designs, any number of colors, that is indeed equivalent to finite state automata, where the colors stand for the states, and the tiles stand for the transitions.

I am assuming you have only a single row of tiles, with the blue at bottom, as seems to be implied by your drawing.

I do wonder whether It helps understanding. Maybe so?

As you said, palindromes do not form a regular set. One disputable intuitive explanation is that palindrome recognition implies counting, and finite state machines cannot count. But there are formal ways of proving that.

The language of palindromes is actually a Context-Free (CF) language. Context-free languages are strictly a superclass to regular languages recognized with finite state automata. So any regular language is context-free, but the converse is false. For example the language of palindromes is CF but not regular.

Thus, **palindromes cannot be recognized with a single row of tiles.**

## What more could be said.

Finite state automaton (FSA) is implicitely the name of a device that has only a finite number of states, used to control a reading head that read-input from left to right on a tape, without ever leaving the input string area, and never writes.

Finite state machines are usually considered as doing the same, except that some can also write on an output tape.

If we are not too attached to established terminology, we could try to relax some of these constraints, while keeping the finite number of states.

A first attempt could be to allow the head to move in any direction.

That gives you what is called a two-way finite state automata. They seem more powerful, but it can be proved that they do no more than FSA (whether deterministic or not).

Another possibility is to allow the automaton to overwrite the tape it is reading, but still without ever leaving the area that was occupied by the input string. This is called a linear bounded automaton (LBA). The LBA is actually one of the most powerful automata there is. They recognize all the context-sensitive (CS) languages, which include the CF languages.

The problem is that they are so powerful that they are difficult to control, analyze or use. But they will recognize palindromes with a finite number of states.

I have been excluding other type of automata which do have a finite number of state for control, but use unlimited memory, which one could perceive as having unbounded number of states.

## Extending the tiling system

In FrankW's answer, it is shown that, by extending the tiling system with several rows, one can recognize palindromes. He has there a very interesting idea, which I am trying to push here.

It can be pushed further. If you allow an arbitrary number of rows, and add a column on each side, it seems that the tiles can actually mimic a linear bounded automaton. Hence, it becomes a very powerful computational system.

I am saying "it seems" because I did not go through all the tedious details of the construction, but only tried to convince myself.

However, rather than go through even the basic aspects of the construction, which are already complex, I will rely on existing results in automata theory.

A row of tiles may be seen as the configuration of a one-dimensional bounded cellular automaton (BCA). Columns represent the evolution of individual cells.

The colors of left and right sides of tiles represent the information exchanged between adjacent cells, while the top and bottom colors represent the state of the cells before and after transitions.

So it seems that a BCA can be simulated by the extended tiling system.

David Milgram showed in 1976 that BCA can simulate a LBA.

Hence the extended tiling system can simulate a LBA.

The extended tiling system is therefore a very powerful computational system, that can recognize context sensitive languages.

Hence **the extended tiling system can recognize palindromes**, among many other things.

Now, I am not giving you the details of the recipe to recognize palindromes and other things in this way, simply because it is very complicated, and no one would read it anyway, if I were able to write it without bugs.

## A set of tiles to recognize palindromes

The general construction is far too complex to be used. However, here is a simple set of tiles to recognize palindromes on the alphabet $\\{0,1\\}$ as requested.

As one might expect it is symmetrical.

R and B stand for red and blue

Matching leftmost and rightmost symbol 1, and removing them

```
 1      1      0     1
R 1    1 1    1 1   1 R
 R      1      0     R

```

Matching leftmost and rightmost symbol 0, and removing them

```
 0      1      0     0
R 0    0 0    0 0   0 R
 R      1      0     R

```

Filling in the sides with fully red tiles

```
 R
R R
 R

```

Creating the bottom line in blue

```
 R
R R
 B

```

But this has nothing to do with finite state machines, as far as I can tell.

# Answer
> 4 votes
The model is more powerful than finite state machines.

If you only allow a single row, you can already simulate a FSM (without $\epsilon$-transitions, but that doesn't restrict their power) by having colors for the states, and tiles for each possible transition:

From the left state on reading the top symbol you go to the right state. (Bottom field is not used and can be filled with any color.)

By using more than one row, we can e.g. add a simple stack:

For each stack symbol $s$, add three colors $s$, $s\_+$, and $s\_-$, also add a neutral color $n$.

Each row of the pattern describes one place in the stack. The color in the right resp. left fields between two symbols of input describes the symbol in the respective cell at that point of the computation. (It's one of the colors $s$, or $n$ if the cell is empty.)

For the tiles in the top row we use the same basic design as for the FSM, but in the bottom field add one of the symbols $s$, $s\_+$, or $s\_-$. $s\_+$ is interpreted as "add $s$ to the top of the stack", $s\_-$ as "remove $s$ from the top of the stack" and $s$ as "$s$ is required to be top of the stack and remains there".

Furthermore we need tiles that manage the stack. There are again three types:

* $s\_+$ on top, $s$ on the right, $t\_+$ on the bottom, and $t$ on the left.
* $s\_-$ on top. $s$ on the left, $t\_-$ on the bottom, and $t$ on the right.
* $s$ on the top, left, and right, $t$ on the bottom.

For each of these types, $t$, $t\_+$, and $t\_-$ many be replaced with $n$ to indicate the bottom of the stack. Also we have all-$n$-tilese to fill the bottom of the pattern below the stack.

Note that this automaton does not have the full power of a PDA, but it is capable of accepting the language of palindromes. I'll leave it to you to construct the specific instance.

---
Tags: regular-languages, finite-automata
---


# Question
Title: Round-Robin Scheduler - What exactly is the quantum time used for?
Suppose you have three stages for a job:

Creation stage = the job gets created

Executing stage = the job is executed/served

Finishing stage = the job is "marked" as finished.

Now, say the quantum time for a round-robin scheduler is 100ms. From what I understand, the 100ms is spent on the executing stage. Am I right to assume that the creation and finishing stage is OS stuff, and what really the quantum time is used on, is the executing time?

I'm a bit confused because I'm trying to write a model, and for the scheduler I'm trying to figure out whether "job 1 was created" counts as a "turn" or consumption of quantum time for that given job. So, if "job 1 was created" happens, then it switches to "executing job2".

I might be mixing up OS tasks and CPU execution here.

# Answer
> 4 votes
For the Round-Robin Scheduler the quantum time is to ensure that each process has a share to the CPU and we don't have starvation problems. It's known for being *fair*, such that each process shares the CPU equality. Quantum time is it's the amount of time spent on each process in the CPU until we context switch to the next process in the ready queue. For example say you have `P1`, `P2`, and `P3` in the ready queue. And some `P4` enters the ready queue at 550ms. The RR would perform something like this:

```
P1 - 0   to 100ms
P2 - 100 to 200ms
P3 - 200 to 300ms
P1 - 300 to 400ms
P2 - 400 to 500ms
P3 - 500 to 600ms [P4 enters]
P4 - 600 to 700ms
... [P1 to P4 cycles]

```

If a process has a CPU-bound execution that is less than the time slice. Then we move to the next process keeping the same time slice. For example let's say `P1` only needs to run for 50ms until it's done. Then you have:

```
P1 - 0   to 50ms [finnished, start P2]
P2 - 50  to 150ms
P3 - 150 to 250ms
P2 - 250 to 350ms
P3 - 350 to 450ms
...

```

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


# Question
Title: Proving that the average case complexity of binary search is O(log n)
I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations. But how would I go about proving that the average case complexity of binary search is O(log n)?

# Answer
> 13 votes
I think most text book will provide you a good proof.

For me, I can show the average case complexity as follows.

Assuming a uniform distribution of the position of the value that one wants to find in an array of size $n$.

* For the case of 1 read, the position should be in the middle so there is a probability of $\frac{1}{n}$ for this case
* For the case of 2 reads, one will read the middle position and then 1 of the 2 other middle positions from the 2 sub-arrays. This probability is $\frac{2}{n}$
* For the case of 3 reads, there are $2\*2$ positions which result in this cost as you go into the 4 sub-arrays of the first 2 sub-arrays. The probability for this cost is $\frac{2^2}{n}$

...
* For the case of $x$ reads, the probability for this case is $\frac{2^{x-1}}{n}$

For the average case, the number of reads will be

$\sum\limits\_{i=1}^{\log(n)} \frac{i2^{i-1}}{n} = \frac{1}{n} \sum\limits\_{i=1}^{\log(n)} i2^{i-1}$

Now you can do integration on an approximation formula which will give you $O(n\log(n))$. Note that $\int\limits\_{1}^{\log(n)} x 2^x dx$ can be calculated and bounded into $\log(n)\*2^{\log(n)} = n\log(n)$ This is a very good way to do that applies to many cases.

Another way to see it can also be $i2^{i-1} \< \log(n) * 2^{i-1}$

Then the formula above is bounded by $\frac{\log(n)}{n} \sum\limits\_{i=1}^{\log(n)} 2^{i-1}$

The summation part is actually $\frac{1 - 2^{\log(n)}}{1 - 2} = 2^{\log(n)} - 1 = n - 1$ which is definitely less than $n$, multiplying this with $\frac{\log(n)}{n}$ gives you what you want $\log(n)$

So you will get the bound as you want $O(\log(n))$

---
Tags: algorithms, time-complexity, average-case, binary-search
---


# Question
Title: Proof that L(M) = {accepts the string 1100 } is undecidable
Let $$L\_\ = \\{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\\}\\, .$$

To proof that the language $L$ is undecidable I should reduce something to $L$, right?

I tried with the classic $A\ TM$, but I could not figure out how to reduce properly.

How I can I proof that $L$ is undecidable?

# Answer
> 0 votes
The usual reduction from the halting problem: for example, the same reduction that shows the zero-input halting problem to be undecidable.

> Suppose you can determine whether a machine $M$ accepts some magic string (such as $1100$). You can then decide whether an arbitrary machine $M$ halts when given input $x$ as follows. Produce a machine $M\_x$ that ignores its input and simulates $M$ running on input $x$. If $M$ halts, $M\_x$ accepts whatever input it was given; otherwise, $M$ doesn't halt so nor does the simulation $M\_x$. So $M\_x$ accepts the magic string if, and only if, $M$ halts on input $x$. Hence, if you could decide whether a machine accepts the magic string, you could decide the halting problem.

---
Tags: turing-machines, reductions, undecidability
---


title: LR(0) expressive power

text:
# Question
Title: LR(0) expressive power
So I have grouped the following formalisms into a power hierarchy (and made classes for them):

## Class 1

* DFA
* NFA
* NFAϵ
* reg.exp

## Class 2 (DCFL expressivity?)

* LR(1)
* DPDA

## Class 3

* CFG
* PDA

## Class 4

* TM
* NTM

Class 4 is the most powerful class and Class 1 is the least powerful. Now I want to compare them to LR(0) parsers. My current intuition is that LR(0) parsers can handle all of Class 1 (and probably belongs to class 1). Class 2 has more power than LR(0) due to the fact that LR(0) defines a subset of Class 2 (DCFL's with the prefix property).

So I guess the question is, should LR(0) parsers be put into its own class or should it go into Class 1 (which would be my guess).

# Answer
You're correct that all regular languages have a LR(0) grammar. Moreover, there are LR(0) grammars which generate a non-regular language. (Exercise: Construct a LR(0) grammar for $\\{ a^n b^n\\,|\\,n\>0 \\}$.)

LR-ness is a tricky concept to get a grasp on, because LR-ness is a property of the *grammar*, not necessarily the *language*. Having said that, it is known that all DCFLs can be recognised by a LR(k) parser in $O(n)$ time. It's also known that any LR(k) grammar can be mechanically transformed into an equivalent LR(1) grammar, and that there are examples for which there is no LR(0) grammar. So LR(1) is the same as DCFL/DPDA, and LR(0) is a proper subset.

So, yes, DCFL/DPDA/LR(1) sits somewhere between 3 and 4 on the Chomsky hierarchy, and LR(0) sits between that and 4. (By the way, don't forget Chomsky type 2 when you're examining hierarchies of languages and machines.)
> 0 votes

---
Tags: formal-languages, automata, parsers
---


# Question
Title: Determine whether there is a valid rounding in a table of numbers
I was told this question would be better suited here:

Suppose you have a table such as:

$\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 &|& 27\\ 1.019 & 2.045 & 0.936 &|& 4\\ 26&22&7&|&55 \end{array}$

Where the rows add up to the numbers on the right and the columns add up to the numbers on the bottom. How can we determine whether there is a valid arrangement of each number using ceiling and floor so that the sum of the rows and columns stays the same? For example, this has a valid arrangement because we can do:

$\begin{array}{ccc} 11 &10 & 3 &|& 24\\ 13 & 10 & 4 &|& 27\\ 2& 2 & 0 &|& 4\\ 26&22&7&|&55 \end{array}$

I'm supposed to use a network flow computation to solve the problem, but I can't figure out a way to arrange the nodes and edges so that I end up "discovering" whether the flow is valid. Do I have to create multiple graphs that each compute a separate flow (e.g. one for each column and one for each row)? I'm guessing that we have to end up with saturated edges at the end of our flow graph, but I'm not sure how to specify the graph so it solves the problem.

# Answer
> 0 votes
You want to translate this into a graph problem (specifically, a network flow problem).

Hint: graphs often arise when you have relationships between two entities. Then each entity becomes a vertex, and each relationship becomes an edge. Do you see anything like that here?

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form
As stated in the title: Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form.

For example: when $p = 2$ and $q = 3$ Next of $2^2\*3=12$ is $2^3=16$ and after that is $2\*3^2=18$

**Question \[edited\]:**

Can this be done in poly-time of the representation of $a$ and $b$?

I believe so and I do have a sketch for this, but I want to see what a "proper" answer to this question is.

# Answer
Let $c = \log p$ and $d = \log q$. Then $\log (p^a q^b) = ca + db$. Define the set $S\_{c,d} = \\{ci+dj : i,j \in \mathbb{N}\\}$. Your problem is equivalent to the following:

> Problem 1. Given $a,b \in \mathbb{N}$ and $c,d \in \mathbb{R}$, find $a',b' \in \mathbb{N}$ so that $ca' + db'$ is the next attainable real number in $S\_{c,d}$ after $ca + db$.

This is in turn equivalent to the following problem:

> Problem 2. Given $\alpha \in \mathbb{R}$ and $X,Y \in \mathbb{Z}$, find $x,y \in \mathbb{N}$ that minimizes $x+\alpha y$, subject to the requirements that $x \ge X$, $y \ge Y$, and $(x,y) \ne (0,0)$.

(The equivalence can be seen by letting $\alpha = d/c$, $X=-a$, $Y=-b$, and $x=a'-a$, $y=b'-b$.)

Problem 2 now amounts to finding the best rational approximation $x/y$ of $-\alpha$, subject to constraints on the size of $x,y$. There are many techniques for that, including continued fractions. You can also express this as the problem of finding a closest lattice point to $(0,0)$ in a certain two-dimensional lattice. There are many algorithms for closest lattice point search in lattices, also known as the closest vector problem; in two dimensions, I believe they run in polynomial time, if I remember correctly. See, e.g., https://mathoverflow.net/q/61897.
> 4 votes

---
Tags: algorithms, number-theory
---


# Question
Title: How do you come up with greedy algorithm for deadline scheduling when comparing x_subscript(i) and y_subscript(k)?
So there are two boxing teams, my team A and the opposing team B, each with m boxers. Based on the player's ranking of skill, x\_subscript(i) being the ranking for ith boxer for team A and y\_subscript(k) being the ranking for kth box for team B. Each fight round is set up one boxer from team A against one boxer from team B at a time. I get to set up who goes against whom, so I need to make sure the boxer from my team A has a higher ranking than the boxer from team B for as many rounds as possible.

I need to provide a greedy algorithm and prove that it's correct, and come up with the running time.

It seems to me it's a type permutation, scheduling with deadlines and apply the inversion, but I am stuck on how to start. Could someone provide a guidace? Thank you!

# Answer
Usually it is easy to identify a few candidate greedy strategies. Once you've got some candidates, try them on some test cases. Try to build a test case (a counterexample) that "kills" each candidate greedy strategy. If you find a test case where a candidate strategy does not give the optimal solution, you can cross that off your list. If you've done a good job at identifying candidates and looking for counterexamples, typically you'll be able to cross off all candidates except for one. Now you have a candidate greedy algorithm -- all you need to do from this point forward is see if you can prove it correct.
> 0 votes

---
Tags: greedy-algorithms, scheduling, permutations
---


title: Master Theorem Questions?

text:
# Question
Title: Master Theorem Questions?
NOTE: I asked this on mathstackexchange, but didn't get the responses I wanted, thought I should post in CS. Sorry if i did something wrong but i am a newbie.

State the asymptotic (worstcase) runtime found by the master theorem. If the master theorem does not apply state why:

1) $T(n) = T(n/3)$

2) $T(n)= 5T(2n/5) + n$

3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$

1) For the first one I think the master theorem does not apply because I do not have a $k$-value, is this enough to show that I can't use the master theorem?

2) For the second one I know $a = 5 , b=2/5, k = 1$, so $\log\_\frac{2}{5}5 \< 1$ so the complexity would be $O(n)$.

3) I don't know how to do, can someone show me?

Can you guys verify whether my answers for 1 and 2 hold true and if possible show me how to deal with 3 if possible using the master theorem?

# Answer
> -1 votes
For (1), try thinking about the problem without using the Master Theorem. Try plugging in some values and see what you get. That would be much more instructive then checking whether the theorem applies (even if that's what the question asks; it's a stupid question in that sense, since it teaches formulaic thinking instead of "open" thinking).

For (3), the Master Theorem applies for an additive term of the form $\Theta(n^k)$; perhaps that's a more general form than the one you've seen in class, and in this case you can try to show that if instead of $n^k$ you have $\Theta(n^k)$ then the Master Theorem applies just as well. (Use the fact that if $f(n) = \Theta(n^k)$ then there exist $a\geq b\>0$ and $N$ such that for $n\>N$, $bn^k \leq f(n) \leq an^k$.)

---
Tags: time-complexity, asymptotics, master-theorem
---


title: Runtime complexity of unary languages

text:
# Question
Title: Runtime complexity of unary languages
I am trying to find a unary language whose runtime complexity is exponential in $n$ (e.g. $\Theta(2^n)$ or a similar expression). But I am not sure how to reason about the runtime of such languages.

I tried the language: $L\_1=\\{1^{2^k}\\}$. This language can be identified by counting the number of ones in the input into a binary register, then checking if the binary register has only zeros and a leading one. This requires $O(n)$ steps to read the input, and probably $O(\log n)$ for each addition, so the total runtime is $O(n \log n)$. Is this correct?

What about the language: $L\_2=\\{1^{2^{2^k}}\\}$? This language can be identified by counting the number of ones in the input into a binary register, then checking if the number of zeros in the register is in $L\_1$. This seems like it can be done in time polynomial in $n$.

How can I construct a unary language that can only be identified in exponential time?

# Answer
Let $L$ be a language in $\mathrm{TIME}(2^{2^n})$ but not in $\mathrm{TIME}(o(2^{2^n}/2^n))$ (such a language exists by the time hierarchy theorem). Define $U = \\{1^n : n \in L\\}$. Using an algorithm for $L$, we get that $U \in \mathrm{TIME}(2^n + O(n^2))$. Running the same argument backwards, we see that $U \notin \mathrm{TIME}(o(2^n/n))$ (here we use that $O(4^n) \ll 2^{2^n}/2^n$).
> 2 votes

---
Tags: time-complexity
---


title: About sorting numbers in linear time

text:
# Question
Title: About sorting numbers in linear time
* If one is given $n$ numbers picked uniformly at random from the interval $\[0,1\]$ then is it possible to sort them in linear time?

It seems to me that some such method exists which uses binary representations of these numbers and compares the sequences of 0s and 1s between any two of them only partially and that somehow is enough!?

What is confusing me is that this somewhere seems to need a source of random bits and that is not clear to me where. How many?

Does one account for the time taken to generate these binary representations?

+ If the numbers are upper bounded by $n$ then apparently there is some probabilistic way of sorting them in linear time with a success guarantee $\geq 1 - \frac{1}{n^c}$ for some constant $c$.

What is this method?

# Answer
> 5 votes
If your input consists of **integers**, that is your elements are from the set $\mathcal{U}=\\{0,\ldots,u-1\\}$, you can sort faster than $O(n\log n)$ assuming your model of computation is the **word RAM**.

* you can sort deterministically (even on using $\text{AC}^0$ computations) in time $O(n \log\log n)$
* there is a randomized algorithm that sorts in $O(n \sqrt{\log\log n})$
* if your *word size* $w=\log u$ is in $\Omega( \log^{2+\varepsilon} n)$ for some $\varepsilon\>0$ then the input can be sorted in linear time

If you are interested in the references, check out Erik Demaine's lecture notes. Note that all these results use in some sense the effect that you can parallelize some computations on the word ram using bit tricks. It does not requires that the numbers are picked uniformly at random from $\mathcal{U}$.

# Answer
> 4 votes
Radix sorting runs in time $O(dn)$ where $d$ is the number of digits in each key and $n$ is the number of keys to be sorted. This is of course linear time only if $d$ is a constant. If the keys are unique and densely packed then $d$ is necessarily $\approx log(n)$, but if there are many repeated keys radix sorting can in theory sort significantly faster than the usual $O(n \log n)%$ methods.

---
Tags: sorting, probability-theory, probabilistic-algorithms
---


# Question
Title: Does a graph always have a minimum spanning tree that is binary?
I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?

# Answer
> 18 votes
There is nothing to be done: for instance, let $S\_k$ denote the star graph with $k$ leaves. The graph $S\_k$ has a unique spanning tree (which is $S\_k$ itself), and it has a vertex with degree exactly $k$.

In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.

---
Tags: graphs, binary-trees, spanning-trees, minimum-spanning-tree
---


title: Sorting with a recursive oracle

text:
# Question
Title: Sorting with a recursive oracle
It is known that the runtime complexity of sorting is $\Theta (n \log n)$. But what if we have, for every input array of size $n$, an oracle that can sort any array of $k\<n$ numbers in constant time?

In this case, the runtime of merge sort becomes $O(n)$. The recursive calls are cheap and the runtime is dominated by the merging step.

Does there exist a more efficient algorithm for sorting, using these oracles? My guess is that the answer is negative, i.e. sorting with recursive oracles has runtime complexity $\Theta(n)$. Is this correct?

NOTE: this is a special case of the following question from cstheory.SE L https://cstheory.stackexchange.com/questions/27094/are-there-problems-for-which-divide-and-conquer-is-provably-useless

# Answer
If you can sort arrays of size $n-1$ then three recursive applications of this sorting procedure are enough, say prefix, suffix, prefix. You can see that using the zero-one sorting theorem, which states that a sorting algorithm works if it can sort zero-one inputs. I leave the case analysis to you.

This algorithm probably works for much smaller $k$. Moreover, it should be the case that given a sorting oracle for $k=cn$ you can sort in $O\_c(1) $ time. One can even guess a formula, $O(c^{-1} \log c^{-1}) $.
> 1 votes

---
Tags: time-complexity, runtime-analysis, sorting, oracle-machines
---


# Question
Title: Where would someone find amortized analysis more useful than average analysis and the opposite?
I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing in each step, while average analysis produces an expected cost based on probabilities.

For them to both exist as separate ways of doing analysis of algorithms, then one must be preferred over the other one in some cases, however I can't figure a case to actually show that.

# Answer
The two are not mutually exclusive. In most situations you're interested in amortized analysis, since usually operations are fast enough so that no user would notice a one time long running time, the real performance being determined by the amortized running time. A good example is garbage collection, essential to many modern computer languages. Garbage collection is extremely slow, but the cost is amortized to be very manageable.

The only notable exception to this is real time applications. For example, if you're operating a hard drive, you need to be fast always. Same goes for some other services provided by the operating system. But that's a specialized area.

Average case analysis is relevant when you can expect the data to be random enough. For example, a long scientific simulation could include a random element, and can be analyzed accordingly. Other data should not be assumed to be random for security reasons. For example, a web server distributing work across other servers can be attacked if load balancing relies only on input randomness.

Sometimes the average case is hard to define. For example, the simplex algorithm and SAT solvers often seen to run much faster than the worst case, but it's hard to attribute this to average case behavior since it's difficult to come up with a relevant average case distribution. Instead, one could point out some relevant features of the input, but doing this rigorously is very hard.
> 3 votes

---
Tags: algorithm-analysis, amortized-analysis, average-case
---


title: Are "Flow Free" puzzles NP-hard?

text:
# Question
Title: Are "Flow Free" puzzles NP-hard?
A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $n \times n$ grid graph such that each vertex is in at most one pair. A solution to such a puzzle is a set of undirected paths in the graph such that each vertex is in exactly one path and each path's set of ends is one of the puzzle's pairs of vertices. This image is an example of a Flow Free puzzle, and this image is an example of a solution to a different Flow Free puzzle.

Is the problem "Does there exist a solution to this Flow Free puzzle?" NP-hard? Does it matter whether $n$ is given in unary or binary?

# Answer
> 6 votes
In the terminology of Nikoli Puzzles this is known as "Nanbarinku" or "Numberlink". The description does not always explicitly mention all squares must be covered, but this is indeed the case in all solutions I checked.

According to Wikipedia Numberlink the problem is NP complete, with reference: Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), NP-Completeness and Enumeration of Number Link Puzzle, IEICE technical report. Theoretical foundations of Computing 109 (465): 1–7

I did not check the fine print.

Added. Following a comment from domotorp, Numberlink usually has an additional constraint. Indeed, quoting from Adcock etal:

> Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the “cover all vertices” constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class.

Adcock et al. Zig-Zag Numberlink is NP-Complete, Journal of Information Processing 23 (2015) 239-245, doi:10.2197/ipsjjip.23.239

---
Tags: np-hard, square-grid
---


title: What if $NP\subseteq BPP$?

text:
# Question
Title: What if $NP\subseteq BPP$?
I'm new to complexity and came upon the following exercise which I'm unable to solve.

Prove that if $NP\subseteq BPP$ then $\Sigma\_2^p=\Pi\_4 ^p$.

# Answer
> 6 votes
Use the Sipser-Lautemann theorem: $\mathrm{BPP} \subseteq \Sigma\_2^p \cap \Pi\_2^p$.

---
Tags: complexity-theory
---


title: Proof of big theta using induction

text:
# Question
Title: Proof of big theta using induction
Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants.

$T(n) = a$, if $n = 2$

$T(n) = 2T(n/2) + cn$ if $n \> 2$ Use induction to prove that $T(n) = \Theta(n \log n)$

Any idea on how to solve this?

# Answer
> 0 votes
Hint: If $T(n/2) \leq M \frac{n}{2} \log \frac{n}{2}$ then $$ T(n) = 2T(n/2) + cn \leq Mn\log \frac{n}{2} + cn \leq Mn\log n +n (c-M\log 2). $$ The lower bound should be similar.

---
Tags: algorithm-analysis, proof-techniques, recurrence-relation, recursion, induction
---