# Question
Title: Selecting a node of a singly-linked list such that the probability of each node being selected is equal
**The Question:** You are given a singly-linked list with *n* nodes that you can only iterate through once at most. You are given additional space to store one node (i.e. a pointer to it). Devise an algorithm that can operate under these conditions, choose/select one node from the list such that the the probability of each node being selected/chosen is equal.

**My Friend's Solution:**

1. Store the first node in the additional space.
2. Move to the next node.
3. Randomly select one node between the one in the additional space and the current node.
4. Store this "winner" in the additional space.
5. Repeat steps 2-4 until the last node in the list is processed.
6. The node stored in the additional space at the end is the one that the algorithm selects.

**My Issue With My Friend's Solution:** Consider the case *n* = 3. There are 2^\*(n-1) = 2^2 = 4 possible ways to go through the list in terms of which node is selected during each iteration of the algorithm:

1. Select 1 -\> from (1, 2) select 1 -\> from (1, 3) select 1 -\> 1 is finally selected
2. Select 1 -\> from (1, 2) select 1 -\> from (1, 3) select 3 -\> 3 is finally selected
3. Select 1 -\> from (1, 2) select 2 -\> from (2, 3) select 3 -\> 3 is finally selected
4. Select 1 -\> from (1, 2) select 2 -\> from (2, 3) select 2 -\> 2 is finally selected

Then, node 3 has a 50% chance of being selected, whereas nodes 1 and 2 each have a 25% chance of being selected.

Intuitively, this makes sense to me; if the first node is not selected while the beginning of the list is being processed, it can never be the one that is finally selected. However, the last node still has a chance of being selected no matter what happens while processing the the rest of the list that comes before the last node.

However, my friend says that my issue with his solution is inconsequential because I didn't model the situation correctly. Can someone tell me where I went wrong?

# Answer
You are absolutely right.

Part of the problem with your friend's solution is that, when he instructs you to make a random choice (in line 3), he did not specify what probability you should use. It's his job to completely specify the algorithm, and not omit details like that. If we choose uniformly at random from the two options, then the algorithm does not work, for the reasons you describe.

It is possible to repair the algorithm by choosing appropriate probabilities at each iteration, but doing this right requires some care.

The standard solution to this is reservoir sampling. (See also Reservoir Sampling - Sampling from a stream of elements for another description of the same algorithm.) You can view reservoir sampling as an instance of your friend's algorithm, but with the probabilities for each random choice specified fully and worked out carefully so that the algorithm does meet the requirements.
> 2 votes

---
Tags: linked-lists
---


# Question
Title: Are there peer-reviewed papers studying the pros and cons of functional programming?
Can somebody refer me to peer-reviewed papers studying the advantages or disadvantages of writing code in a functional style? Are there papers which discuss the applications of Lambda Calculus in fields such as Machine Learning, Language Design, etc.?

# Answer
There is a famous paper "Why Functional Programming Matters" by John Hughes. The main argument of this paper is the modularity of functional programs.

Also, the work by Chris Okasaki about functional data structures is very interesting. The article "Red-Black Trees in a Functional Setting" provides a very clear implementation of red-black trees using functional programming language, which is much simpler than their imperative implementation in the book "Introduction to Algorithms" by Tomas H. Cormen et al.
> 7 votes

# Answer
a semifamous high quality, free reference in this area is Structure and intepretation of computer programs by Abelson and Sussman, MIT professors, some more info on wikipedia. they advocate functional programming as a way of understanding the theory and abstraction of programming such that understanding of functional programming will help one understand/apply the same principles in any language. they make some effort to discriminate it from/juxtapose it with what is called "imperative style" but without side-by-side comparisons.
> -1 votes

---
Tags: reference-request, programming-languages, lambda-calculus, functional-programming
---


# Question
Title: Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$
So, it's fairly easy to prove that if $L \in DCFL$, then $L \Sigma^\* \in DCFL$. Basically, you take the DPDA accepting $L$. You remove all transitions on final states, and then for each $a \in \Sigma$ and each final state $q$, you add a transition looping from $q$ to $q$ on $a$.

I'm using this in a paper, and I'd love to not have to actually prove this construction is valid. It's easy, but it's about a half-page long. Since DPDAs have been studied almost exhaustively, I was wondering, does anybody know of a paper that proves this property?

# Answer
One of the early works on DCFL is Seymour Ginsburg, Sheila Greibach: *Deterministic context free languages*, Information and Control, Volume 9, Issue 6, December 1966, Pages 620–648, doi:10.1016/S0019-9958(66)80019-0

The paper has various closure properties, for instance closure under complement (mind that my old Hopcroft and Ullman book states ".. was observed independently by various people") and closure under quotient with regular languages.

Closure of DCFL under concatenation with regular languages is the result you need, which is Theorem 3.3 from the paper.
> 4 votes

---
Tags: formal-languages, reference-request, automata, closure-properties, pushdown-automata
---


# Question
Title: Do undecidable languages exist in constructivist logic?
Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't allow for proof by contradiction.

I'm wondering, is anyone familiar with how this affects results regarding Turing Machines and formal languages? I notice that almost every proof that a language is undecidable relies on proof by contradiction. Both the Diagonalization argument and the concept of a reduction work this way. Can there ever be a "constructive" proof of the existence of an undecidable language, and if so, what would it look like?

EDIT: To be clear, my understanding of proof by contradiction in constructivist logic was wrong, and the answers have clarified this.

# Answer
> 19 votes
Yes. You don't need the excluded middle to derive a contradiction. In particular, diagonalisation still works.

Here is a typical diagonalisation argument by Conor McBride. This particular diagonalisation is about incompleteness, not undecidability, but the idea is the same. The important point to notice is that the contradiction he derives is not of the form "P and not P", but of the form "x = x + 1".

Of course, now you might be wondering whether constructive logic admits "x = x + 1" as a contradiction. It does. The main property of a contradiction is that anything follows from a contradiction, and using "x = x + 1", I can indeed constructively prove "x = y" for any two natural numbers.

One thing which might be different about a constructive proof is the way in which "undecidable" is defined. In classical logic, every language must either be decidable or undecidable; so "undecidable" simply means "not decidable". In constructive logic, however, "not" isn't a primitive logical operation, so we cannot express undecidability this way. Instead, we say that a language is undecidable if assuming that it is decidable leads to a contradiction.

In fact, even though "not" isn't a primitive in constructive logic, we typically define "not P" as syntactic sugar for "P can be used to construct a contradiction", so a proof by contradiction is actually the only way to constructively prove a statement of the form "not P" such as "language L is undecidable".

# Answer
> 9 votes
When talking about provability of classical statements constructively it often matters how we formulate them. Classically equivalent formulations do not need to be equivalent constructively. Also it matters what you exactly mean by a constructive proof, there are various schools of constructivism.

For example, a statement stating that there is an uncomputable total function would not be true in those flavors of constructive mathematics which presume the Church-Turing Thesis (i.e. every function is computable) as an axiom.

On the other hand, if you are careful you can formulate it such that it is provable: for any computable enumeration of total computable functions, there is a total computable function which is not in the enumeration.

You may found this post by Andrej Bauer interesting.

ps: We can also look at diagonalization from category theoretic perspective. See

# Answer
> 4 votes
I *think* that the cardinality proof still holds, demonstrating the existence of languages that aren't computable languages (so definitely undecidable).

The immediate proof is pretty straight forward, it simply observes that Turing Machines are encoded in some finite alphabet (might as well be binary), so there's countably many, and the set of all languages over a fixed alphabet (might as well be binary again) is the set of all subsets of the set of strings over that alphabet - i.e. the power set of a countable set, and must be uncountable. Therefore there's less Turing Machines than there are languages, so something is not computable.

This seems to me to be constructive enough (although it would be impossible to pursue physically, it gives you a way of pointing at some set of languages and knowing one is not computable).

We might then ask whether it's possible to show that countable and uncountable sets have different cardinality, in particular, avoided diagonalisation. I think this is still possible. Cantor's original argument seems to also be suitably constructive.

Of course, this really needs to be checked by someone who knows much more about constructivist logic.

# Answer
> 3 votes
I think I agree with others that the diagonalization argument is constructive, although from what I can tell there is some disagreement about this in some circles.

I mean, assume that we're looking at the set of all decidable languages. I can construct an undecidable language using diagonalization. It's worth noting that I don't consider "constructivism" and "finitism" to be the same thing at all, although historically I think these were related arcs.

First, I think everybody - even constructivists - agree that the set of decidable languages is countable. Since the set of Turing machines is countable (we can encode all valid TMs using finite strings), this agreement follows pretty easily.

Since the set of decidable languages is countable, we can assume some enumeration of these languages: $L\_1, L\_2, ..., L\_k, ...$. Here's a procedure that will generate a language not in the set:

1. Consider the string $0^i$.
2. If $0^i \in L\_i$, then our language should not contain $0^i$.
3. If $0^i \notin L\_i$, then our language should contain $0^i$.

After the $n$th step, our language cannot be any of the languages $L\_1, L\_2, ..., L\_n$. After an arbitrary (or potentially infinite) number of steps, we can't have found a language in the set to match the one we've just constructed.

So technically, we've constructed a language that is "not decidable"; whether a constructivist would argue that "not decidable" shouldn't be confused with "undecidable" is an interesting question, but one which I am ill-equipped to answer.

To clarify, what I think this demonstrates is the following: we can constructively prove that there exist languages not decided by Turing machines. How you choose to interpret that within a particular framework is a harder question.

---
Tags: formal-languages, turing-machines, logic, proof-techniques, undecidability
---


# Question
Title: Decision problems in $\mathsf{P}$ without fast algorithms
What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known algorithm is "slow".

Here are two examples:

* **Recognition of perfect graphs.** In their FOCS'03 paper \[1\] Cornuéjols, Liu and Vuskovic gave an $O(n^{10})$ time algorithm for the problem, where $n$ is the number of vertices. I'm not sure if this bound has been improved upon, but as I understand it, more or less a breakthrough is needed to obtain a faster algorithm. (The authors give an $O(n^9)$ time algorithm in the journal version of \[1\], see here).
* **Recognition of map graphs.** Thorup \[2\] gave a rather complex algorithm with the exponent being (about?) $120$. Perhaps this has been even dramatically improved upon, but I don't have a good reference.

I'm especially interested in problems that have practical importance, and obtaining a "fast" (or even a practical) algorithm has been open for several years.

---

\[1\] Cornuéjols, Gérard, Xinming Liu, and Kristina Vuskovic. "A polynomial algorithm for recognizing perfect graphs." Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on. IEEE, 2003.

\[2\] Thorup, Mikkel. "Map graphs in polynomial time." Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on. IEEE, 1998.

# Answer
Perhaps the following problems fit into your examples:

* (The decision version of) Coloring, Clique, Stable Set, Clique Covering in perfect graphs. So far, the only known polynomial time algorithms for these problems are based on the ellipsoid method, which is ''slow'' (and numerically unstable).
* AKS-primality test in $O((\log n)^{12})$ time. Though many improvements (currently $O((\log n)^{7.5})$), the AKS-algorithm is still too slow in practice.
> 12 votes

# Answer
There's a similar question over on cstheory, with lots of examples ranging from the "realistically impractically slow" algorithms with exponents of 6 or 7 upwards. That question also discusses large constants too.

There's one classic that I want to reproduce as it seems like such a spectacularly horrible example of polynomial time (shamelessly stolen from JeffE's answer):

***Corollary 1. The number of steps in our algorithm is at most $1752484608000n^{79}L^{25}/D^{26}(\Theta\_0)$.***

***Corollary 2. The number of steps in our algorithm is at most $117607251220365312000n^{79}(\ell\_{max}/d\_{min}(\Theta\_0))^{26}.$***

From: Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O’Brien, An Energy-Driven Approach to Linkage Unfolding, SOCG 2004.
> 11 votes

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


# Question
Title: How can I produce a summation function from this set of production rules for a grammar?
I am not entirely sure if the title is the correct way to phrase what is occurring. There is a recurring process which I decided to attempt to model using production rules similar to those used in a context-free grammar.

The real world process is a production line. It takes 1 unit, after 2 weeks, produces 1 unit, after 4 weeks, that unit will produce another unit - and also 2 of the starting units. After 4 weeks the "another unit" will produce "that unit" - and also 3 of the starting units. This continues semi indefinitely, but the range I am looking at is roughly 52 weeks.

I came up with this model of production rules

$S\rightarrow A$

$A\rightarrow S^2B$

$B\rightarrow S^3A$

I attempted to expand this so that I could formulate a generating function and solve for n=52 (52 being the 1 year mark).

$S$,$A$,$S^2B$,$S^5A$,$S^7B$, ...

However, I was unable to determine if I was taking the correct approach to solving this situation. I believe that an error here lies in the fact that the duration of time is ignored. Namely that from $S\rightarrow A$ 2 weeks elapse, from $A\rightarrow S^2B$ 4 weeks elapse, and from $B\rightarrow S^3A$ 4 weeks elapse.

In order to better understand this situation, I decided to code an example so I could at least see the totals. However, it did not lend itself to producing a summation function.

So, given all this, how is it possible to come up with a summation function instead of having to manually iterate through it like this c# approach does? Or, is there a similar/alternate approach to modeling this which will allow an easier summation process?

Please feel free to correct any misunderstandings I may have.

**edits**

For example:

Week 1: We have 1 unit (S). It sits for 2 weeks until it is ready to become 1 of the next type(A).

Week 3: The first unit is now here. It sits for 4 weeks until it is ready to become 1 of the next type(A). At that time, it also becomes 2 of the first type(S).

Week 7: The unit from Week 3 has now become 2 of the first type of unit(S). It also created 1 of the second type(A). The 2 units of type S will now sit for 2 weeks until they make 2 units of type A. The 1 unit of type A will now sit for 4 weeks until it makes 1 unit of type B and 2 units of type S.

Week 9: The 2 units of type S from week 7 have now sat for 2 weeks. Now they have become 2 units of type A. These two units of type A will sit for 4 weeks and produce 4 units of type S and 2 units of type B.

Week 11: The 1 unit of type A from week 7 has now sat for 4 weeks and has now made 1 unit of type B and 2 units of type S. The 1 unit of type B will sit for 4 weeks and then make 1 unit of type A and 3 units of type S. The 2 units of type S will now sit for 2 weeks and make 2 units of type A.

Also, the 2 units of type S from week 9 have now sat for 2 weeks and become 2 units of type A. These two units will sit for 4 weeks and become 2 units of type B and will also become 6 units of type S.

etc.

This can perhaps be represented by a series of recurring relations

$s(n) = a(n) + b(n) + c(n)$

$a(n) = 2\*b(n-4) + 3\*c(n-4)$

$b(n) = a(n-2) + c(n-4)$

$c(n) = b(n-4)$

where

$s(n) = a(n) = b(n) = c(n) = 0$ for $n \< 1$

$a(1) = 1$

# Answer
OK, so the question now has a set of recurrence relations. To solve these, you can plug them in to each other until you get a single recurrence relation. First, substitute $c(n)=b(n-4)$ to get rid of all of the $c$'s: $$a(n) = 2 b(n-4) + 3 b(n-8)$$ $$b(n) = a(n-2) + b(n-8).$$

Now substitute in to get rid of the $a$'s:

$$b(n) = 2 b(n-6) + 3 b(n-10) + b(n-8).$$

So, you've gotten down to a single recurrence relation for the $b$'s. Solve this using standard methods; see Solving or approximating recurrence relations for sequences of numbers for details. Then, once you have a solution for the $b$'s, you can reverse the substitutions and obtain a solution for the $a$'s, $c$'s, and finally $s$'s.

If you want to find an exact equation for the $b$'s (rather than an asymptotic estimate), the method of generating functions will probably be useful. You'll have to find the roots of a 10th-degree polynomial ($x^{10} - 2 x^4 - x^2 - 3$, I think), and the solution will likely be an expression of the form $c\_1 r\_1^n + \dots + c\_{10} r\_{10}^n$ where $r\_1,\dots,r\_{10}$ are the roots and $c\_1,\dots,c\_{10}$ are the appropriate constants. This might get a bit messy, but it should be doable.

Or: You can ask Wolfram Alpha to solve the recurrence relation for you. Sometimes it is able. Unfortunately, for this one it seems to have failed: output.
> 3 votes

# Answer
I'm not sure I understand the problem, but it sounds like rabbits: once rabbits get old enough, they breed and give birth to baby rabbits (which some time later again breed and give birth to yet more rabbits, etc.) -- treating the rabbits as immortal. It sounds like we could treat each unit as a rabbit. The classic Fibonnaci sequence arises out of a situation like this.

Have you tried to write a recurrence relation? Let $f(n)$ denote the number of units after $n$ weeks; can you express $f(n)$ as some simple function of $f(n-1),f(n-2),\dots,f(1)$? If so, there are standard techniques for solving recurrence relations.

**Update:** Here is an attempt at an recurrence relation, based upon the description of the process you gave. Let $s(n)$ denote the number of units of type S that newly appeared on week $n$, and $a(n)$ the number of units of type A that newly appeared on week $n$ (neither of these include any units that were previously created). If I understand your rules, it's something vaguely along these lines:

* $a(n) = s(n-2) + a(n-4)$,since a newly created unit of type S sits for 2 weeks, then becomes one of type A; and a newly created unit of type A sits for 4 weeks, then becomes one of type A (and 2 of type S)
* $s(n) = 2 a(n-2)$ (since a newly created unit of type A sits for 4 weeks, then becomes two of type S (and one of type A)
* $s(1)=1$, $a(1)=1$, and $s(n)=a(n)=0$ for $n\<0$.

If this is correct, you can solve these mutual recurrence relations using standard relationships.

I suspect these recurrence relationships might not be exactly what you had in mind, because the rules that I stated might not accurately capture exactly the process you had in mind, but I'm not sure how to fix them, because I still don't understand the rules of your process. I suggest you start by writing down more clearly the rules of the process, then try to define recurrence relations like these. I suspect it's all clear in your mind how the process works, but you haven't figured out how to write it down very clearly yet. The process of figuring out how to write it down clearly and precisely forces you to think carefully about the process and will be beneficial to you. So, I suggest you take some time to do that, then edit your question accordingly.
> 2 votes

# Answer
In order to count properly, you need the grammar to terminate, i.e. generate words. This still allows you to properly model "semi-indefinite", that is arbitrarily long production runs. So maybe use this grammar which assumes that production may end at any point in time:

$\qquad\begin{align} S &\to A \mid \varepsilon \\ A &\to S^2 B \mid \varepsilon \\ B &\to S^3 A \mid \varepsilon \end{align}$

Now we want to count

* the number of produced units (by type S, A, B) and
* the number of weeks used.

We can apply the straight-forward translation and add a parameter for weeks:

$\qquad\begin{align} S(w,x,y,z) &= x z^2 A(w,x,y,z) + 1 \\ A(w,x,y,z) &= w^2 y z^4 B(w,x,y,z) + 1 \\ B(w,x,y,z) &= w^3 x z^4 S(w,x,y,z) + 1 \end{align}$

Note how we count units of type S, A and B in the exponents of $w$, $x$ and $y$, respectively. The exponent of $z$ tracks the number of weeks. Now solve the equation system for $S(\\\_)$.

Is this the generating function for the quantity you wanted? Let's see: $\[w^k x^m y^n z^j\]S(w,x,y,z)$ is the number of *linear interleavings* of production so that $k$ S-units, $m$ A-units and $n$-B units are produced over the course of $j$ weeks.

I guess that in your setting (which sounds like 3D-printer reproduction) you assume that all available units produce *in parallel*. In this case, the framework of formal grammars and generating functions in general as used here won't be of help since it can only deal with *additive* measures.

Instead, we can set up a (multi-dimensional) set of interleaved recurrences:

$\qquad\begin{align\*} S\_0 &= S\_1 = (1,0,0) \\ S\_n &= (1,0,0) + A\_{n-2} \\ \phantom{.} \\ A\_0 &= A\_1 = A\_2 = A\_3 = (0,1,0) \\ A\_n &= (0,1,0) + 2S\_{n-4} + B\_{n-4} \\ \phantom{.} \\ B\_0 &= B\_1 = B\_2 = B\_3 = (0,0,1) \\ B\_n &= (0,0,1) + 3S\_{n-4} + A\_{n-4} \end{align\*}$

Addition $+$ denotes component-wise addition. Now, if $S\_n = (s,a,b)$ then you have (at most) $s$ objects of type $S$, $a$ of type $A$ and $b$ of type $B$ after $n$ weeks.

By the way, $S\_{52} = (73018, 55866, 22659)$. You better get a large greenhouse.
> 2 votes

---
Tags: context-free, formal-grammars, combinatorics
---


# Question
Title: Time complexity of a backtrack algorithm
I've developed the following backtrack algorithm, and I'm trying to find out it time complexity.

A set of $K$ integers defines a set of modular distances between all pairs of them. In this algorithm, I considered the inverse problem of reconstructing all integer sets which realize a given distance multiset. i.e. :

Inputs: $D=\\{p\_i−p\_j \mod N, i≠j \\},K $
Output : $P=\\{p\_1,p\_2,...,p\_K\\},\qquad p\_i \in \\{0,1,2,...,N-1\\},\qquad p\_i \> p\_j $ for $i\>j$

Simply saying, the algorithm puts $K$ blanks to be filled. Initially, puts 1 in the first blank. For the second blank it looks for the first integer that if we add to P, it doesn't produce any difference exceeding the existent differences in $D$. Then, it does so, for next blanks. While filling a blank if it checked all possible integers and found no suitable integer for that blank, it turns back to the previous blank and looks for next suitable integer for it. If all blanks are filled, it has finished his job, otherwise it means that there weren't any possible $P$'s for this $D$.

Here's my analysis so far. Since the algorithm checks at most all members of $\\{2,...,N\\}$ for each blank (upper bound) there is $N-1$ search for each blank. If each visited blank was filled in visiting time, the complexity would be $O((K-1)(N-1))$ since we have $K-1$ blank (assuming first one is filled with 1). But the algorithm is more complex since for some blanks it goes backward and some blanks may be visited more that once. I'm looking for the worst case complexity i.e. the case that all blanks are visited and no solution is found.

# Answer
> 6 votes
The running time of your algorithm is at most $N (N-1) (N-2) \cdots (N-K+1)$, i.e., $N!/(N-K)!$. This is $O(N^K)$, i.e., exponential in $K$.

Justification: There are $N$ possible choices for what you put into the first blank, and in the worst case you might have to explore each. There are $N-1$ choices for the second blank, and so on. You can draw a tree of the choices made: the first level shows the choice of what to put in the first blank, the second level shows the choice of what to put in the second blank, and so on. The degree of the root is $N$; the degree of the nodes at the second level is $N-1$; and so on. The number of leaves is the product of the degrees at each level, i.e., $N (N-1) (N-2) \cdots (N-K+1)$. In the worst case, your algorithm might have to explore every possible node in this tree (if it is not able to stop early before reaching the $K$th level and backtrack from a higher-up node). Therefore, this is a valid upper bound for the running time of your algorithm.

If you want a tighter analysis, here is the exact worst-case running time (not an upper bound). The number of leaves in your search tree, in the worst case, is the number of strictly increasing sequences of length $K$ over $\\{1,\dots,N\\}$ that start with 0. (We can assume without loss of generality that the first blank contains a 0, as you point out, which is why we can restrict to sequences that start with a 0.) That number is exactly $C(N-1,K-1) = (N-1)!/((K-1)!(N-K)!)$.

This is a tighter analysis, but it doesn't save us from exponential running time. When $N\gg K$, $C(N-1,K-1)$ is still $O(N^K)$, i.e., exponential in $K$.

That said, evaluating your algorithm experimentally (by testing it on some real data sets) would probably be a better way to evaluate your algorithm than trying to derive a worst-case running time. You might want to compare it to the performance of translating your problem into a SAT instance and using an off-the-shelf SAT solver. Depending upon the value of $N$ and $K$, there might be other better alternatives as well.

See also the following question for a closely related problem, and for algorithms to solve it:

# Answer
> 2 votes
My first piece of advice is to eliminate your GOTOs. They make analysis of algorithms quite difficult, and are generally considered bad practice in programming.

Here are some overall strategies:

Can you find a bound on the number of times each loop runs? Try to prove these bounds, possibly by induction on your input size.

To determine the complexity of a loop, this formula generally holds:

loopTime = (times loop was run) * (complexity of loop body).

Note that this doesn't hold for your code because of the GOTOs, which is why refactoring is highly recommended.

---
Tags: algorithms, algorithm-analysis, combinatorics, search-algorithms, greedy-algorithms
---


title: Why every finite set is computable?

text:
# Question
Title: Why every finite set is computable?
According to wikipedia, every finite set is computable. Definition: set $S \subset N$ is *computable* if there exists an algorithm which defines in finite time if a given number $n$ is in Set.

Question: what is wrong with this counter-example:

* given some $TM$
* $S \subset N$
* Lets assume $S$ could contain only $0$, i.e., either $S = \\{0\\}$ or $S = \emptyset$
* if a given $TM$ halts then $S=\\{0\\}$ otherwise $S=\emptyset$

So set $S$ is finite, but not computable, since we cannot "compute" if a given $TM$ halts.

What is wrong above?

# Answer
> 6 votes
A similar question was answered here:

How can it be decidable whether $\pi$ has some sequence of digits?

We can ignore the question "if a given TM halts" as it is irrelevant what the question actually is, let's just name the condition `C`.

If `C` is true, then the correct algorithm is `if n == 0 return true else return false`. If `C` is false, the correct algorithm is `return false`. Whether C is true or false, one of these two algorithms **is correct for every n**, so such an algorithm exists.

Additionally, "does a given TM halt" is computable for the same reason - the correct algorithm is either `return true` or `return false`. What is not computable is a function that answers "does this TM halt" for any TM.

# Answer
> 2 votes
The problem is, you haven't defined a language. You have defined a function that returns a language.

What you call $S$ is really $S(M)$, for some Turing Machine $M$. What is undecidable is the function problem: given a Turing Machine $M$, determine $S(M)$.

Once you have a fixed $S$, deciding which numbers are in this $S$ is always decidable if $S$ is finite. This is because all finite languages are regular. If $L = \\{w\_1, w\_2, \cdots, w\_n\\}$, then the regular expression $R = w\_1 + w\_2 + \cdots + w\_n$ accurately describes $L$.

# Answer
> 0 votes
The simplest answer I can think of: because we can make a finite look-up table for answers. In other words, if you have a finite language $L = \\{w\_0, \ldots, w\_{k-1}\\}$, consider the following algorithm:

Input: $x$
$L \leftarrow \[w\_0, \ldots, w\_{k\_1}\]$
for $i$ from 0 to k-1 do
$~~$ if $x = L\[i\]$
$~~$$~~$ accept
reject

Now, the problem with your argument is that you are thinking of $M$ as input in one place and not thinking of it as input in another place. If $M$ is not part of the input then the machine does not decide the halting problem but only a fixed instance of it, so the algorithm for deciding it doesn't imply that the halting problem is decidable.

Note that we don't need to *construct* (uniformly in $M$) the algorithm deciding the halting of a given machine $M$, we only need to show that it *exists*, i.e. the process of finding the machine that decide if $M$ halts or not does not need to be a computable process (and it can't, if it could then your argument would go through).

On the other hand, if we assume that $M$ is a part of the input, then the set is not finite anymore. It is essentially $A = \\{\langle M,b\rangle \mid \text{$b=0$ and $M$ halts}\\}$. What you are doing is taking a slice of this set $B\_M = \\{ w \in A \mid \mathsf{fst}(w)=M \\}$ which is finite and therefore decidable. But the decidability of all slices of a set does not imply the set itself is decidable. We need to be able to decide membership in $A$ uniformly in $M$, i.e. we need a single algorithm that works for all $M$, not a different algorithms for each $M$.

---
Tags: computability, turing-machines
---


# Question
Title: Number of distinct substrings in a string
From what I have come to understand, the best way to implement it is to use the suffix array $S$ of the string $w$ and its LCP-array (Longest Common Prefix) $L$.

The answer can be obtained by

$$ \sum\_{i=1}^{|w|} \left( |S\[i\]| -L\[i-1\] \right).$$

What I don't get is how and why is this working?

I would be very grateful if someone explained this.

# Answer
Instead of a formal proof, I want to give some intuition behind the formula. The suffix array contains all the suffixes of the string $w$. A substring is nothing else than a prefix of a suffix. So if you count $\sum\_i |S\[i\]|$, you will get all the substrings, but of course you overcount the number of *different* substrings.

Let's have a closer look. Assume the $S\[i-1\]=xyz$ and $S\[i\]=xyxyz$. By the above counting method the entry $S\[i-1\]$ counted the substrings $x,xy$ and $xyz$ and the entry $S\[i\]$ counted $x,xy,xyx,xyxy,xyxyz$. You will notice that since the prefixes of length 2 of both entries are the same we have double counted $x,xy$. But the length of the longest common prefix is stored in $L\[i\]$ so we subtract it to compensate for the overcounting.
> 3 votes

---
Tags: algorithms, data-structures, strings, substrings, suffix-array
---


# Question
Title: Find disjoint contiguous sub-arrays in better than $\mathcal O(n^2)$
Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.

The sub-arrays should not overlap and it can not be empty.

eg \[2 -1 -2 1 -4 2 8\]

ans (-1 -2 1 -4) (2 8)

diff = 16

Better than $\mathcal O(n^2)$ solution was expected.

# Answer
> 2 votes
*This is a complete re-edit of my previous solution, which erroneously focused on partitions, not on arbitrary sub-arrays.*

This problem seems to be an interesting variation on the Maximum subarray problem, which consists of finding the subsequence of values with the largest sum in an array.

Given an array `a` of integers, finding the maximum subarray can be done as follows:

```
int best_left = 0, best_right = -1, best_sum = INT_MIN;
int i, curr_left = 0, curr_sum = 0;
for ( i = 0 ; i < N ; i++ ) {
    curr_sum += a[i];
    if ( curr_sum < a[curr_left] ) {
        curr_sum = 0;
        curr_left = i+1;
        }
    else if ( curr_sum > best_sum ) {
        best_left = curr_left;
        best_right = i;
        best_sum = curr_sum;
        }
    }

```

The above code is untested. The largest summing interval should then be `[best_left,best_right]`.

To solve your problem, you could sweep from left to right and store the values `best_left` and `best_sum` for each position `i` in the array, effectively giving you the largest sub-array from `0` to `i` for each `i`.

At the same time, you could flip the signs in the above code and also store the *minimum* subarray from `0` to `i` for each `i`.

Now imagine doing the same thing again, yet this time traversing the array backwards, from right to left, also storing the minimum and maximum subarrays as you go along.

Once you've constructed both sets of indices, you can traverse them and find the point which partitions the array such that the difference between the minimum/maximum subarray on either side is largest.

---
Tags: algorithms, optimization
---


# Question
Title: Does the empty language have a CFG in CNF?
I just not sure does empty set have a context-free grammar in Chomsky normal form?

That is, for $B=\emptyset$, then a context-free grammar is $S \to S$, I think which doesn't have a Chomsky normal form. I am not sure. Can some one explain?

# Answer
> 4 votes
Note that *every* context-free language has a grammar in CNF (that is proven) and $\emptyset$ is context-free, so the answer is clearly: yes!

Do you get from $S \to S$ to it, using the normal transformation algorithm? No, because the usual algorithm requires a reduced, chain-rule free grammar as input; yours does not fit.

Approach one: use the algorithms (from lecture or textbook) to remove the chain rule, and try again!

Approach two: start with another grammar that fulfills the criteria!

> Approach two is doomed to fail for most grammars: in order for a grammar to derive not a single word, it can not have any rules that are *not* thrown out by reducing. Thus, the only (kind of grammar) that works is $(\\{S\\}, \Sigma, \emptyset, S)$, that is a grammar with no rules at all. Note that it is in CNF.

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


# Question
Title: What constitutes one unit of time in runtime analysis?
When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?

# Answer
> 6 votes
When doing complexity calculations we generally use RAM model. In this model we *assume* that array indexing is O(1). Assignment statement is just like assigning some value to some variable ins *array of variables*. This is just for convenience. It simplifies analysis of the algorithm. In real world array indexing takes $\approx$ O(log I) where I is number of things indexed.

We generally consider things that depend on size of input e.g. loops. Even if there is O(1) operation in the loop and it is executed n times then algorithm runs for O(n) time.

But O(1) operation outside of loop take only constant time and O(n) + O(1) = O(n).

Read about radix sort algorithm from CLRS.

# Answer
> 5 votes
The ultimate goal is "execution time in seconds" or more generally (disregarding modern CPU features) "number of clock cycles". As it turns out, this is *hard* to analyse, and it is also machine or at least instruction-set specific. Therefore, it is usually not done.

The next level of abstraction is to precisely count all operations (of some assembly-style pseudo code), keeping individual operation cost (in clock cycles) as parameters. Note that such analysis is found in Knuth's "The Art of Computer Programming" among others, so there certainly is a place for this kind of approach, even though it is hard and tends to be harder in presence of memory hierarchy.

Last but not least -- and certainly most prominent -- is analysis of dominant operations ignoring constant factors and asymptotically vanishing constributions ("$O$-analysis"). The reasoning is that runtime is bound to behave asymptotically like the number of most frequently executed operations, times some factor depending on the actual implementation and machine. This kind of analysis yields general results that apply to all machines (covered by the RAM model) and is easier to perform than the above. It can, however, lack specifity.

Leaving "classic" frameworks behind, many algorithms are dominated by memory and/or communication cost, so in that case counting the number and volume of memory acceses resp. network transmissions is reasonable (and maybe sufficient).

Furthermore, keep in mind that we are often not that interested in absolute performance of an algorithm but in comparing it to others. This, too, may inform the choice of analysed parameter.

So you see, there is no one definite answer. Depending on the goals of the analysis at hand, different answers can be given.

See also my answer here for some related thoughts, and Sebastian's answer on Quicksort for an example.

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


# Question
Title: "Last Come => More Relevant" data structures
As I think of data structures I studied and dealt with, they are all optimized to retrieve/put a random element, to perform optimally based on unspoken assumption that each element has equal odds of being asked for (e.g. Red-Black trees).

By the nature of my program, I need to maintain an online dictionary of items that typically serves items that were added last.

That is, the later an item has been added, the higher the likelihood of it being retrieved back in the nearest future.

Speaking more formally, let's define a set $S$ of pair $(k\_i, d\_i)$, where $k\_i \in K $ and $K$ has a comparison operator $\leq$ defined, $d\_i \in D$. Let $p(k)$ be the probability of our need to retrieve pair $(k, d)$.

What is an efficient way to store $S$ with regard to function $p$ ?

# Answer
I think of three possible options:

1. As mentioned before in the comments, one of my all-time favorite data structure, splay-trees. They are easy to implement and probably (assuming the *Dynamic Optimality* conjecture is true) roughly as good as any other dynamic search tree data structure. We already know that splay trees are as good as any static search tree. Note that there are other types of dynamic binary search trees (tango trees, zipper trees, ...), which will also perform well compared to the best dynamic search tree.
2. Use one or more optimal binary search tree (via dynamic programming). Since you insert/delete elements you need to rebuild the search tree form time to time. Say after a threshold value of elements that change you build the new optimal tree from scratch. This might be applicable, if you have time between the request. The rebuilding can be also be done in the background. Since building a optimal search tree is $O(n^2)$, this is not a good idea for large data sets.
3. Use Hashing. It might not treat the later inserted elements different, but in practice it might be as good as the other ideas.

You might think of keeping the last inserted elements in a separate data-structure (like a hash-map ) which you query first. Of course, from time to time you need to rebuilt.
> 5 votes

# Answer
You can use caching.

Just remember the last element inserted. O(1) when last element is queried. You can also keep list of latest k elements inserted.

And use any good data structure that the language you are using provides. O(log n) for balanced tree based data structure.
> 3 votes

# Answer
Have a look at treaps. A treap is a binary search tree with respect to keys and a heap with respect to a second element parameter ("priority"). That is, if you insert new elements with a higher priority than all already present keys (e.g. by using an increasing counter) those element inserted most recently stay at the top of the tree, thus enabling fast access.

If your access patterns are more dynamic than that, self-adjusting data structures such as splay trees or self-organising lists may be better. Note that you can easily make treaps self-adjusting by changing priorities accordingly when elements are accessed.
> 1 votes

---
Tags: data-structures, search-trees
---


# Question
Title: Recurrence formula for a known sequence?
Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries:

1 7 7 7 7 9 9 9 7 9 9 9 7 9 9 9 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 7 11 11 11 11 13 13 13 11 13 13 13 11 13 13 13 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15 9 13 13 13 13 15 15 15 13 15 15 15 13 15 15 15

Origin/background of Problem: These number are generated from a divide and conquer algorithm. For example if we have a 8 bit binary-string and we are asked to find the location of 1's in minimal number of questions then, the above sequence is the # of questions asked for each possible binary 8-bit word i.e from 00000000, 00000001 ....11111111 the corresponding # of questions are elements of above sequence i.e 1,7,..15, respectively.

Algorithm:

Lets take 0000 0001, for instance:

1) First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.

2) Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?

3) Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.

4) This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

# Answer
Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=00010101$. Then the sequence is $$ 0111, 11, 1, $$ and so $N = 6$ and the cost is $13$.
> 1 votes

---
Tags: combinatorics, recurrence-relation
---


# Question
Title: Algorithm to shrink a DFA by introducing nondeterminism?
This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question.

I'm doing research where I'm trying to find the structure of complements of a certain class of finite languages. It's easy for me to get the minimal DFAs accepting these languages, but I'd like to examine what kind of structure NFAs accepting these langauges have, particularly how nondeterminism helps with state-size of the automata (the DFAs are exponentially large).

The problem is, the main NFA reduction technique uses equivalences, which won't produce any reduction if I start with a minimal DFA (since it's basically using the same technique). If I start with a non-minimal DFA, it just spits out the minimal DFA.

What I'm wondering is, are there algorithms which can start with a DFA, and shrink it into a smaller NFA by introducing nondeterminism? Are there "standard techniques" to do this?

I have found preorder reductions, which look promising but hard to implement. I'm open to many suggestions.

# Answer
For efficient heuristics I'd suggest looking into the CAD literature on the state encoding problem (assigning binary identifiers to states of a DFA to minimize the amount of logic for the state transition function.) Devadas and Newton, "Decomposition and factorization of sequential finite state machines," *IEEE TCAD*, 8(11):1206-1217, 1989 points out that there is a close relationship between state encoding and state machine decomposition.

If for a DFA with $N$ states you assign a unique $M$ bit state identifier to each state ($\lg\_2N \< M\leq N$), then you have essentially decomposed the DFA into a network of $M$ interacting two-state machines. Equivalently: you have defined a set $S$ with $M$ elements, and assigned a unique subset of $S$ to each state in your original DFA. This is also what the Rabin-Scott powerset construction algorithm does. So by doing a state encoding on the DFA we are trying to reverse engineer the set that the powerset construction algorithm started from.

In the traditional state encoding problem all encodings are legal, and there is some objective function (related to the amount of logic in the state transition function) that you are trying to minimize. To generate an NFA you need to solve a constrained version of the enconding problem where:

> an encoding of $M$ bit identifiers to the DFA states represents an NFA iff for each symbol in the alphabet the transition function for each bit is a simple disjunction of bits. (No conjunction or negation is allowed.)

So you could enumerate all the $M$ bit encodings for all $\lg\_2N \< M\leq N$, and check whether each one satisfies the constraint. (Note that for $M=N$ the trivial "one-hot" encoding always satisfies the constraints, and gives you the DFA.) The enumeration is ridiculously large though, (Di Micheli's textbook gives it as something like $\frac{2^M !}{(2^M - N)!M!}$.) The reason I'm suggesting the CAD literature is that there are techniques for doing this search implicitly rather than enumerating (for example, by using BDDs, see Lin, Touati and Newton, "Don't care minimization of multi-level sequential logic networks," *Int'l Conf Comp-Aided Dsgn* ICCAD-90:414-417, 1990.

**Example**

Take the following DFA, (with a state encoding that I derived by cheating (I generated the DFA from an NFA using Rabin-Scott, and the encoding represents the subsets chosen by Rabin-Scott.))

If we call the bits in the state assignment ABCD, then when the input symbol is 1, the transition function is A=A, B=A, C=B, D=C. When the input symbol is 0, the transition function is A=A, C=B, D=C. This is a purely disjunctive transition function with no conjunction or negation, so this state encoding gives us an NFA. The states in the NFA correspond one-to-one with the bits in the encoding, and the transition function is as given:

**Formulation as boolean satisfiability problem**

The informal description above leads directly to an encoding as a boolean satisfiability problem. There is a set of variables that describes the transitions in the NFA, and a set of variables for the DFA state encoding that would be derived from Rabin-Scott for the chosen NFA. The transitions of the specific DFA you are trying to decompose are used to place constraints on the NFA transitions.

Suppose we are given a DFA with $N$ states for a language with $S$ symbols, and we would like to derive an $M$ state NFA, with $\lg\_2N\<M\leq N$. We will use the variables $y\_{sft}$ to represent the possible transitions in the NFA. $y\_{sft}$ will be true iff there is a transition in the NFA *from* NFA state $f$ *to* NFA state $t$ on *symbol* $s$. In the above example NFA, the alphabet is of size 2 and there are 4 NFA states, so there are $SM^2=32$ $y$ variables and $y\_{0AA}, y\_{1AA}$, and $y\_{1AB}$ are all true while $y\_{1DA}$ is false.

We will use the variables $x\_{dn}$ to indicate whether or not the Rabin-Scott algorithm should include NFA state $n$ in the set of states labeling DFA state $d$. In the example above we have $N=8$ DFA states and $M=4$ NFA states so there are 32 $x$ variables. In the example above suppose the bottom-most state (the one labeled "1011") is state $k$, then $x\_{kA}$, $x\_{kC}$, and $x\_{kD}$ are true while $x\_{kB}$ is false.

Now the constraints. First of all, Rabin-Scott must find a different encoding for each DFA state, so for the DFA states $i \< j$ and all NFA states $\\{A,B,\cdots, D\\}$: $$ (x\_{iA} \neq x\_{jA}) + (x\_{iB} \neq x\_{jB}) + \cdots + (x\_{iD} \neq x\_{jD}). $$

Next it must be the case that if Rabin-Scott found a transition from DFA state $i$ to DFA state $j$ on symbol $s$ then for each NFA state $k$ included in the encoding of $j$ there must be an NFA state $l$ from the encoding of DFA state $j$ such that the original NFA had a transition from $l$ to $k$. In the example above, on symbol "1" there is a DFA transition from DFA state "1000" to DFA state "1100" so there *must* be an NFA transition from NFA state A to NFA states A and B and *no* NFA transition from NFA state A to either NFA state C or D. So for each of the $o(SN^2)$ edges in the DFA we have the constraints: $$ \begin{eqnarray\*} x\_{jA} & = & y\_{sAA} x\_{iA} + y\_{sBA} x\_{iB} + \cdots + y\_{sDA} x\_{iD} \\ x\_{jB} & = & y\_{sAB} x\_{iA} + y\_{sBB} x\_{iB} + \cdots + y\_{sDB} x\_{iD} \\ & & \cdots \\ x\_{jD} & = & y\_{sAD} x\_{iA} + y\_{sBD} x\_{iB} + \cdots + y\_{sDD} x\_{iD}. \end{eqnarray\*} $$

Finally we need to deal with the start and accept states. The DFA start state is encoded with the union of the NFA start states, so the DFA start state better not be encoded with the empty set, so $x\_0A + x\_0B + \cdots + x\_0D$. And finally we need a set of variables $f\_n$ to indicate whether each NFA state is an NFA accept state. It must be the case that the encoding for every DFA accept state contains at least one NFA accept state and that the encoding for every DFA non-accept state contains no NFA accept states so: $x\_{iA}f\_A + x\_{iB}f\_B + \cdots + x\_{iD}f\_D$ for DFA accept states $i$ and $\neg (x\_{jA}f\_A + x\_{jB}f\_B + \cdots + x\_{jD}f\_D)$ for DFA non-accept states $j$.
> 4 votes

# Answer
Minimising NFAs is hard, so hard indeed that even approximation is hard; see Minimizing NFA’s and Regular Expressions by Gramlich and Schnitger (2005). This article seems to have some useful references, too, e.g. NFA Reduction Algorithms by Means of Regular Inequalities by Champarnaud and Coulon (2002) which contains minimisation techniques.
> 3 votes

# Answer
There exists some notions of *canonical* FSAs that are not necessarily deterministic, hence *can* be smaller than the minimal DFA. One example is the "Residual" FSAs, for which one can compute canonical residual FSAs quite directly, see F. Denis, A. Lemay, and A. Terlutte. "Residual finite state automata", *Fundamenta Informaticae* 51(4):339-368, 2002. Several alternatives exist.
> 2 votes

---
Tags: formal-languages, automata, finite-automata, discrete-mathematics, nondeterminism
---


# Question
Title: How a program is copied to RAM from harddisk
I know that for executing a program, it should be copied to RAM. But the problem is whole of it may not be copied always.

Since the size of the RAM is limited, there is mechanism called virtual memory. If the addressed thing is not in memory, a page fault occurs and the data is copied to the RAM. My question is who keeps track of which data is in the RAM and not in the RAM?

# Answer
The operating system (with help from the CPU) keeps a *page table*, which is a mapping of each virtual page for to the physical page it is mapped to. The page table also includes a bit for whether a particular page is currently mapped. For every load and store instruction the hardware walks the page table (or at least a cached portion of it.) If the virtual page is currently mapped to a physical page, the hardware figures this out and returns the right data.

If the virtual page is currently unmapped then the operating system receives an interrupt. At this point it looks into the *memory map* for the process. This is a list of ranges of virtual memory, the permissions that should be applied to that range, and the file (if any) on disk that stores the data from that range when it is not in RAM. Typically for the main executable there will be a text segment, data segment and sometimes a read-only data segment (for constants), as well as a bss (zero initialized data) segment, a stack, and the heap managed by `malloc`. There may be (usually are) additional text and data segments for each shared object (shared library) that the program needs to load.

You can use `mmap()` to tell a Posix operating system to create a new region in the memory map, the permissions for that region, and which file to use to back that region. On Linux, for an existing process you can get a listing of its currently mapped regions using the `pmap` command.
> 5 votes

---
Tags: operating-systems, memory-management, virtual-memory, memory-access
---


title: Finding path with minimum weight

text:
# Question
Title: Finding path with minimum weight
There is a river which can be considered as an infinitely long straight line with width W.

There are A piles on the river, and B types of wooden disks are available. The location of the $i$-th pile is $(X\_i, Y\_i)$.

The $i$-th type of wooden disks has radius $R\_i$, and its price is $C\_i$ per disk.

Disks can be placed on the river such that for each wooden disk, its center must be one of the locations $(X\_i, Y\_i)$ of piles. We can only move on the wooden disks.

How to find the minimum cost such that we can cross the river.I am unable to approach questions like these. What would be the best method to approach this one?

I have come to realize that we can use Dijkstra's algorithm here. We treat this as a graph, with piles as the nodes. Start point can be $y=0$. and $y=W$ as the end point. But i am having implementation problems. There are multiple disks which can be used in going from on state to another. How to handle this?

# Answer
I'm sure someone will manage to come up with a more efficient idea, but here's a basic one:

1. Have both sides of the river be nodes in the graph. Define the disk used for these nodes as having 0 cost and 0 radius.
2. Split each pile into B nodes in the graph, one for each type of disk.
3. Connect each pair of nodes where the sum of the radius of the 2 disks of these nodes is less than or equal to the distance between the nodes.
4. Define the cost of an edge as the cost of the disk of the destination node. The cost of the source node will already have been included in the previous step.
Note that this should be dynamically calculated - one can approach an edge from either side, thus it can take on the value of either node, thus could have different costs at different times.
5. Run Dijkstra's algorithm as per usual from the source side of the river.

One can get a more efficient but more complex algorithm by only having a single node for each pile and storing the radius of the chosen disk at each point.

Note that any disk type A with cost cA and radius rA can be discarded if there exists a disk type B with radius rB \>= rA and cost cB \<= cA, or, equivalently, if there's a bigger and cheaper disk type, since it would always be more efficient to use that one instead.
> 1 votes

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


title: Minimum cost closed walk in a graph

text:
# Question
Title: Minimum cost closed walk in a graph
Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices?

Does this problem have a name? I tried to reduce this to similar problems (in particular the traveling salesman problem) to see if it was NP-hard, but was unsuccessful.

Here's an example:

Then a possible closed walk is: A,B,C,D,C,B,A, with a cost of 6.

Thanks!

# Answer
> 2 votes
Using this answer, by finding the minimum cost closed walk (or just it's cost) of an arbitrary 4-regular planar graph, with weights 1, we can decide whether it has a Hamiltonian Path, but this problem is NP-complete. So the original problem is NP-hard.

# Answer
> 3 votes
This problem is equivalent to TSP. Compute all pairwise shortest distances between the vertices in the given graph $G$. Then take the complete graph $K\_n$ that is weighted with the shortest-distances of the original graph $G$. The TSP tour of the complete graph corresponds to the shortest min-cost closed walk.

More precisely, a shortest tour $\pi$ in $K\_n$ decodes a closed walk in $G$: just replace every edge $(u,v)$ in $\pi$ by the shortest path from $u$ to $v$. Clearly, the costs are preserved. Assume that there would be a shorter closed walk in $G$. Select select the vertices in order they appear first. This permutation implies a tour in $K\_n$ (maybe even shorter than the closed walk in $G$), hence we have a contradiction.

See the figure for your example.

---
Tags: algorithms, graphs, np-hard, graph-traversal, traveling-salesman
---


# Question
Title: Computer science problems related to music?
Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a scale or a tonality or general what is considered harmony in frequencies and physics, electromagnetism and waveforms.

Can you give examples of the area I want to know of?

For instance, given an algorithm that guesses a melody, how successful will the melody be in resembling an artist or likewise decision problem that could be feasible or what do you think?

# Answer
> 6 votes
It is easy to think of many different problems:

1. Converting sound to scores.
2. Converting scores to sound.
3. Automatic music composition.
4. Music analysis, for example key recognition.
5. Music classification, such as style recognition and artist recognition.

All of these things are actually being done.

# Answer
> 4 votes
music is a nice/neat/natural way to approach some very advanced CS algorithms/applications etc. and there has been a large burst of innovation and crosspollination between the two areas in the last decade especially in computer music software.

one important area involves attempting to separate different channels from a mixed sound. in other words suppose separate tracks are mixed together into a single track (separate instruments, vocals, etc). its actually a very advanced statistical/AI problem of separating out the original tracks from the mixed track. another basic application is attempting to remove vocals only from music; there are devices advertised to do this, some of them highly engineered and expensive, called *vocal removers*. this same problem arises in other guises in statistics. my understanding is that ICA, independent component analysis can be used to solve this problem.

another interesting area of application of CS to music related to vocals, enjoying a massive surge in use in the last decade: *pitch correctors* or so-called autotune which adjust vocal pitch to discrete, on-key increments. Autotune has an origination in scientific/statistical/mathematical analysis; from wikipedia:

> Auto-Tune was initially created by Andy Hildebrand, an engineer working for Exxon. Hildebrand developed methods for interpreting seismic data and subsequently realized that the technology could be used to detect, analyze, and modify the pitch in audio files.\[3\]

also, audio plugins for effects, or "effects boxes", often involve many highly advanced CS/signal processing concepts, closely connected to algorithmic and mathematical theory, such as Fourier Transforms, etcetera. another common effect with some algorithmic theory/complexity is reverb which has roots in mathematical convolution.

ref \[3\] from wikipedia with more on autotune & Hildebrand: The Gerbils Revenge / Auto-Tune corrects a singer’s pitch. It also distorts—a grand tradition in pop., Sasha Frere-Jones, New Yorker 6/9/2008

# Answer
> 3 votes
There is a machine information retrieval (MIR) field that is concerned with retrieving information from music. You may find interesting paper "Machine Learning Approaches for Music Information Retrieval" by Tao Li et al. which describes several problems in MIR and corresponding machine learning approaches:

* Emotion detection in music.
* Music style identification.
* Music recommendation (for example, for playlist generation).

Another good paper is "Contextual music information retrieval and recommendation: State of the art and challenges" by Marius Kaminskas et al. which also describes the already mentioned MIR problems and:

* Querying music by example
* Querying music by humming

PhD thesis "Music Recommendation and Discovery. In the Long Tail" by Òscar Celma Herrada is a terrific resource and I personally enjoyed the slides.

Finally, MIR summer school will be soon organized. The registration is already closed, but you may find interesting the materials of this school.

---
Tags: probability-theory, decision-problem, probabilistic-algorithms
---


# Question
Title: Number of Combinations of Connected Bipartite Graphs
Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?

Obviously there are $2^{n m}$ different set of edges but many will be disconnected.

# Answer
The answer is was given by David Eisenstadt in his answer to my question.

The answer can be computed by starting with the fully connected bipartite graph and evaluating the Tutte polynomial at (1,2).

While I don't fully understand everything about this problem, the intuitive reasoning is as follows:

Start with the fully connected-graph. The Contraction-Deletion Algorithm and the Tutte polynomial at (1,1) give the number of possible spanning trees. But we are actually not interested in the number of spanning trees but also along all the still-connected graphs along the paths to get to the spanning trees.

# Note:

If you can explain this further, either add your own answer, or edit mine. If you add your own answer, I will accept yours.
> 0 votes

---
Tags: graphs, combinatorics
---


title: BPP upper bound

text:
# Question
Title: BPP upper bound
does $BPP\subseteq P^{NP}$ ? it seems reasonable but I don't know if there is a proof of this!could any one post a proof or any material that discusses the statement or something that look like this .

# Answer
> 5 votes
It's open whether $\mathsf{BPP} \subseteq \mathsf{P}^{\mathsf{NP}}$.

The best we can currently say about $\mathsf{BPP}$ is that it is contained in S2P, a class contained in $\Sigma\_2 \cap \Pi\_2$ and $\mathsf{ZPP}^{\mathsf{NP}}$. See references given at Wikipedia.

If $\mathsf{BPP} \subseteq \mathsf{P}^{\mathsf{NP}}$, then this fact does not relativize (Stockmeyer, On Approximation Algorithms for #P).

---
Tags: complexity-theory, complexity-classes, randomized-algorithms, oracle-machines
---


# Question
Title: Runtime of searching for a number in an array?
Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire array, which is O(n).

But how about in the case where we know the number definately exists in the array? Does the runtime change then?

Also is there a way to find out the average number of searches it would have to do before a number is found in an array based on its size?

# Answer
> 3 votes
Regardless of whether the number is present in the array, all n elements will still be examined in the worse case. For example if searching for the number 5:

```
array1 = {6, 8, 3, 7, 8, 2}
array2 = {6, 8, 4, 9, 4, 5}

```

Searching array1 will require looping over all 6 elements (leading to 5 not being found). Searching array2 will also require examining all 6 elements, with the final element being 5 and the search returning true.

As for the average number of searches, I believe you are referring to the average number of elements examined? This is difficult. If you are wondering what the average case is for arrays of ints with length 6, you would need to generate all possible permutations of arrays of ints with length 6, then search them all for your desired number (say 5) and calculate the average. This will differ again if you only include permutations that have at least one element which is 5 (average will improve).

For a brute force search algorithm like this, all you can really be certain of is that the average case will be somewhere between the best best case O(1) (5 is first element of the array) and the worst O(n)

# Answer
> 2 votes
The general idea for proving similar lower-bounds is what is called adversary arguments.

Let's assume we have an algorithm that check at most $n-2$ cells. We argue that the algorithm cannot be correct.

Consider an array $A$ which does not contain $x$. We will fix $A$ to have an $x$ later. We run the algorithm on $A$. When the algorithm finishes it has checked at most $n-2$ cells. Therefore there are two cell $a$ and $b$ which are not checked. The algorithm run on $A$ will return some answer. We now modify $A$ such that the algorithm will work as before and clearly returns an incorrect answer.

If the algorithm returns $a$ we put $x$ in $b$. If the algorithm does not return $a$ we put $x$ in $a$. In both cases the modified $A$ contains $x$. However, note that the algorithm never checks the value of $a$ or $b$, so this change in $A$ has no effect on algorithm's execution. Therefore, the algorithm run on modified $A$ will return the same answer that it was returning before the modification. But we modified $A$ such that the answer returned by the algorithm is incorrect. So the algorithm doesn't work correctly.

The only thing we assumed about the algorithm was that it accesses at most $n-2$ cells of the array. Therefore, no algorithm with this assumption can solve the problem correctly. In other words, any algorithm solving the problem correctly needs to check at lease $n-1$ cells.

This is called an adversary argument because we look at the execution of the algorithm on some input and adversely modify the input to make sure the algorithm fails.

This $n-1$ lower-bound is tight as there is an algorithm that checks the first $n-1$ cells and returns the correct answer (if we have seen $x$ in the these cell then we know the answer, if we haven't, then b assumption that $x$ is in $A$ we know that it must be in the last cell).

---

### Average case:

The part above was for the worst-case analysis of deterministic algorithms. In principle one can use similar but more delicate adversary arguments to prove average-case lower bounds on deterministic algorithms (average case analysis of deterministic algorithms should not be confused with randomized algorithms). However, remember that we don't have *the* average case analysis. Average case analysis depends on the distribution of inputs that you assume. Below I will consider a two simple but usual distribution.

The general idea is to show that there are many inputs where the algorithm check too many cells.

---

I. The input is an array of size $n$ containing exactly one $0$ and $x=0$. All inputs are equally likely.

Note that the average number of cells checked by linear search is roughly $n/2$. We show that this is tight up to a constant factor and no algorithm can have a better average case. Note that there are $n$ possible inputs each with probability $1/n$.

Assume that there is an algorithm that solves the problem. Consider the execution of the algorithm on all $0$ array. (This is not a possible input that we are interested in, however we can run the algorithm on whatever we like). The algorithm will check some number of cells. We consider the first $n/2$ cells that it checks (they don't need to be the first cells of the array). Let me call these cells $S$. Now consider all possible inputs that have zeros in these cells. There are roughly $n/2$ possible inputs of this form. We argue that for $n/2-1$ of these the algorithm needs to check at least $n/2$ cells. If stops before checking $n/2$ cells, and returns some answer, that answer should work for all of these inputs. However, the answer cannot be correct for more than one of them. These $n/2-1$ inputs contribute $1/n * n/2 * (n/2-1)$ to the total average number of cells that algorithm checks. So independent of how the algorithm runs on other possible inputs, the average will be at least $n/4-1$.

---

II. Now assume that we have arrays filled with $0$ and $1$ and there can be any number of them, and all are equally likely. W.l.o.g. let's assume $x=0$. Note that there are $2^n-1$ inputs.

The linear search algorithm checks on average $$\sum\_{k=1}^{n-1} k2^{n-k}2^{-n} = O(1)$$ cells. So in this case we cannot prove any non-trivial lower bound.

# Answer
> 1 votes
Searching time in array might be faster the $\mathcal O(n)$ but such searches uses some knowledge about that array.

For instance there is something like Binary search algorithm which have much better complexity of searching for element. However this search method assumes that array is sorted in ascending order. Thanks to this assumption binary search works in $\mathcal O(\log n)$ but you need to take some extra effort to store this array sorted at all time.

However if array is arbitrary then it's a bit more complicated.

Let's start with something called Online algorithm. More precisely let's take a look on list update problem. In this problem you assume that some search queries might occur more often then other so it would be more efficient to update list/array when search is made. This will let you to reduce search time if some elements are searched much more ofthen then other.

Now let's look back at the original problem, searching arbitrary array, having no knowledge about it structure. It should be obvious that searching element in array has time complexity $\mathcal O(n)$, but can we be more precise on this? In fact we can, it involves some probability theory and basic calculus. It's quiet fun to do this by yourself so I'll just point out steps which you need to take in order to calculate avarage number of elements examined.

1. Assume that array contains unique elements from 1 to $n$.
2. Assume that all permutations of elements are equally probable, so each permutation has probability $\frac{1}{n!}$.
3. Write down search procedure and determine how many times each step will be executed.
4. Find general formula for any length of array.

You can also computer someting called Probability-generating function which is usefull for analysis of algorithms.

As for book reference on that topic I can recommend The Art of Computer Programming by Donald Knuth.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, search-algorithms, arrays
---


title: How to do Big 'O' notations

text:
# Question
Title: How to do Big 'O' notations
How can I solve $\mathcal{O}$-notations without using Java or any other programming language?

I only want to use pen and paper.

# Answer
I assume that you want to solve the following problem:

Given two functions $f(n)$ and $g(n)$, with, let's say, $g, f: \mathbb{N} \to \mathbb{R}$.

Question: *Is $f(n) \in \mathcal{O}(g(n))$?*

You can recall the definition of the $\mathcal{O}$-notation from e.g. Wikipedia, which tells you that

$$f(n) \in \mathcal{O}(g(n)) \quad\text{if and only if}\quad\exists n\_0 \in \mathbb{N}, c \in \mathbb{R}: f(n) \le c\cdot g(n) \text{ for all } n \ge n\_0.$$

This reduces the given problem to a merely analytical one. You have to develop some intuition here whether or not the answer to your question will be "yes" or "no".

If you think that $f(n) \in \mathcal{O}(g(n))$, then you can show this by starting from $f(n)$ and formulate inequalities of the form $f(n) \le ... \le c\cdot g(n)$ which may potentially only hold for sufficiently large numbers. The maximum of those "sufficiently large numbers" then will be your $n\_0$.

In order to show the contrary, i.e. $f(n) \not\in \mathcal{O}(g(n))$, you would have to show that there are **no** such $n\_0$ and $c$, which is considerably harder. Probably, you will prove that $\limsup\_{n \to \infty} \frac{f(n)}{g(n)}$ does not exist.
> 3 votes

# Answer
Follow this really good example. There is no Big-O using any programming languages.

Link : https://stackoverflow.com/questions/5791146/big-o-big-oh-notation-problem

If you don't understand it, edit your question appropriately so we can better help you.
> 0 votes

---
Tags: algorithms, formal-languages, terminology, regular-languages, asymptotics
---


# Question
Title: How to solve this Planning Domain Definition Language (PDDL) question?
These are 5 action descriptions with conditional effects:

> Action(A, Precond:{X}, Effect:{when P : ~X), Z})
>
> Action(B, Precond:{Y}, Effect:{when Z : ~P), ~Y,~Z,X})
>
> Action(C, Precond:{~Z}, Effect:{when P : ~X), Y})
>
> Action(D, Precond:{~X}, Effect:{when Q : X)})
>
> Action(E, Precond:{Z}, Effect:{when Q : ~Z)})

**What state would result from executing the action sequence \[E,D,A,B,C\] in the state {P,Q,Y,Z}?**

I know the answer but I really don't know how to achieve it. Anyone please shed some light? (Please include workings)

# Answer
I will turn my comment into an answer. Recall that if your state is $\\{P,Q,Y,Z\\}$, and an effect of an action is $\sim\\!Z$ (from now on written $\neg Z$), then the new state will *not* contain $Z$, i.e., the state will be, if nothing else is an effect, $\\{P,Q,Y\\}$.

Since the question asks what the result of a sequence of actions will be, we need to solve this in the order of that sequence. The sequence asked was $\[E,D,A,B,C\]$, and the state was $\\{P,Q,Y,Z\\}$? Observe that we by *square brackets* denote a *sequence* (i.e., an ordered list) and by *curly brackets*, an unordered set (the usual kind).

Action $E$ in state $\\{P,Q,Y,Z\\}$: Precondition $Z$ is good since $Z$ is in the state. Effect is "when $Q$, $\neg Z$". The new state will thus be $\\{P,Q,Y\\}$. We omit writing $\neg Z$ since every element *not* occurring in the state will be assumed to be not held.

Action $D$ in state $\\{P,Q,Y\\}$: Precondition $\neg X$ is good. Effect: "when $Q$, $X$". Hence new state will be $\\{P,Q,X,Y\\}$.

Action $A$ in state $\\{P,Q,X,Y\\}$: Precondition is good, $X$ is in the state. Effect: "when $P$, $\neg X$, and $Z$". $P$ is in the state, hence we remove $X$ and we also add $Z$. New state is $\\{P,Q,Y,Z\\}$.

Action $B$ in state $\\{P,Q,Y,Z\\}$: Precondition $Y$ is good. Effect "when $Z$, $\neg P$, also $\neg Y$, $\neg Z$ and $X$". $Z$ is true, hence we lose $P$. We also lose $Y$ and $Z$ and gain $X$. New state is $\\{Q,X\\}$.

Action $C$ in state $\\{Q,X\\}$: Precondition is $\neg Z$, so good. Effect: "when $P$, $\neg X$, and $Y$". This is the first time we encounter an implication in which the antecedent $P$ is false, so we don't remove $X$. We still add $Y$, though. Hence the new, and final state is $$ \\{Q,X,Y\\}. $$
> 4 votes

---
Tags: artificial-intelligence
---


title: Inductive vs. recursive definition

text:
# Question
Title: Inductive vs. recursive definition
When should I call a definition recursive and when should I call it inductive?

I have read Carl Mummert's nice answer on MSE. So if I understand correctly we refer to definitions of objects like natural numbers, lists, trees, etc. as inductive whereas we refer to definitions of operations over objects like $+$ or $head$ or $leftchild$ as recursive.

Is this the correct way to distinguish these in programming languages theory?

Are there examples where using either would make sense?

# Answer
An inductive definition takes some elementary objects of the structure to be defined and combines those to obtain new elements of said structure.

**Example**: Definition of the syntax of many logics.

On the contrary, a recursive definition is a rule how to obtain a specific object based on somehow "smaller" objects of the same structure.

To see the difference more clearly, consider the following: To define the valid arithmetical expressions, you would state something like

* Any real number is a valid arithmetical expression
* When $\varphi$ and $\psi$ are valid arithmetical expressions, so are $(\varphi + \psi)$, $(\varphi - \psi)$, etc.

This is an inductive definition of arithmetic expressions, as you build up the class of valid expressions from the bottom (base cases) upwards. Recursion, on the other hand, works from the top to the bottom. In this case, you would *recursively* check whether an arbitrary string is a valid expression or not.

When you define an object recursively, the object is determined by easier to compose objects of the same structure, like the Fibonacci numbers. You can only get the value of $\text{Fib}(n)$ by knowing $\text{Fib}(n-1)$ and $\text{Fib}(n-2)$.
> 3 votes

---
Tags: terminology, programming-languages, logic, recursion, inductive-datatypes
---


# Question
Title: Do fully optimizing compilers for terminating programs exist?
In Andrew W. Appel's book, *Modern Compiler Implementation in ML*, he says under chapter 17 that *Computability theory shows that it will always be possible to invent new optimizing transformations* and proceeds to prove that a *fully optimizing compiler* will solve the halting problem: A program *Q* that produces no output and never halts can easily be replaced by its optimal representation, *Opt(Q)*, being "L: goto L". So a fully optimizing compiler can solve the halting problem.

So my question is this: **Does a fully optimizing compiler exist for terminating programs?** My only thoughts are the following: Even though a program is guaranteed to terminate, it can still be arbitrarily complex, and for any concrete optimizing compiler, C, one could perhaps construct a program that takes C as input and somehow produces a worse program as some kind of corner case.

Also, **What are the implications of restricting ourselves to terminating programs?**

# Answer
> 19 votes
I assume you are interested in optimisation of runtime. As I've written in my comment, that does not sufficiently specify the goal: does an optimisation reduce runtime on *any* input, *every* input, all *worst-case* inputs or even *on average*?

I will show that all of them are impossible. The proof extends to optimising the length of the program.

Recall that the following problem is not computable:

> Given a context-free grammar $G$ with terminal alphabet $\Sigma$, decide whether $\mathcal{L}(G) = \Sigma^\*$.

Note furthermore that given a context-free grammar $G$, we can hardcode, say, the CYK algorithm for that one grammar; denote this algorithm by $\mathrm{CYK}\_G$. We observe that $\mathrm{CYK}\_G$ terminates for all inputs (from $\Sigma^\*$).

Now assume that there is an optimiser $\operatorname{Opt}$ which, given an always terminating algorithm $A$, outputs a result-equivalent algorithm which is optimal with respect to runtime. Clearly,

$\qquad \operatorname{Opt}(\mathrm{CYK}\_G) = \text{'}\mathtt{return\ true;}\text{'} \iff \mathcal{L}(G) = \Sigma^\*$

and we have thus constructed a decider for an uncomputable problem, contradicting the assumption.

---
Tags: computability, compilers, program-optimization
---


# Question
Title: Generate random numbers from an interval with holes
Given a set $S$ of $k$ numbers in $\[0, N)$. The task is to randomly generate numbers in the range $\[0, N)$ such that none belongs to $S$.

**Edit** \- Also given an API to generate random numbers between $\[0, N)$. We have to use it to randomly generate numbers in the range $\[0, N)$ such that none belongs to $S$.

I would also like a generic strategy for such questions. Another one I came across was to generate random numbers between \[0,7\] given a random number generator that generates numbers in range \[0, 5\].

# Answer
> 1 votes
```
0 1 2 3 4 5 6 7 8 9

0 1 2 3 - 5 - 7 8 -

```

"-" are in $S = \\{4,6,9\\}$

You can create mass distribution with $$\text{Prob}(x) = \begin{cases}\frac{1}{N - |S|} & \text{if } x \notin S\\ 0 & \text{if} \ x \in S \end{cases} $$

and then use this algorithm. Copied from here.

```
from collections import defaultdict
import random

def roll(massDist):
    randRoll = random.random() * sum(massDist) # in [0,1)
    s = 0
    result = 0
    for mass in massDist:
        s += mass
        if randRoll < s:
            return result
        result+=1

sampleMassDist = [1,1,1,1,0,1,0,1,1,0]

d = defaultdict(int)
for i in range(1000):
  d[roll(sampleMassDist)] += 1

print d

```

# Answer
> 1 votes
If $k$ is small (and smaller than $N$) you can generate a number $t$ in $\[0,N)$ and test that it is not in $S$ before returning it. If $t$ is in $S$ (bad luck), you retry until you eventually succeeds. This is very simple and will do in many practical situations where $k$ is small and where is it easy to test for membership in $S$.

Another approach is to pick a number $t$ in $\[0,N-k)$ and then compute and return the $t$-th number in $\[0,N)\setminus S$. This is good when $S$ has a form simple or regular enough (e.g., the powers of 3) and it is easy to compute how many elements in $S$ are below some value. It is good also when $N$ is not too large, say $N\sim 100$, and you can precompute the $t$-th numbers.

---
Tags: algorithms, probability-theory, sampling, random-number-generator
---


# Question
Title: Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing
I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form *return any leaf of $T$ that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$?* More informally, the restriction is that when the edge is given, we can only proceed in to that direction.

I can simply perform a DFS and return a leaf found. I think this would take $O(d)$ time, where $d$ is the diameter of $T$. However, I'd like to answer a query in $O(1)$ time. Moreover, I'd only like to allow linear preprocessing time. My idea for achieving this was to use a DFS, label leaves, and then label edges when the search backtracks. This idea might work with some additional effort, but I'm really unsure about the details.

"Graph reachability" turned up some results, but maybe they are dealing with more complex problems. I'm happy with any method that uses $O(n+m)$ preprocessing time and answers the queries in $O(1)$ time.

# Answer
> 5 votes
Yes, I think you can do this in $O(1)$ time. I outline a method below. There's probably a simpler way to do it, but the following should suffice.

**Preprocessing.** I'll assume we can view your tree as a rooted tree, with some root. In pre-processing, annotate each internal node $w$ with one example of a leaf that is a descendant of $w$. This can be done in $O(n+m)$ pre-processing time, using a very simple top-down traversal (DFS).

Also, define $p^\*(\cdot)$ recursively as follows: if $w$ has any siblings, then $p^\*(w)=w$; otherwise, $p^\*(w)=p^\*(v)$ where $v$ is the parent of $w$; and $p^\*(r)=r$, where $r$ is the root of $T$. In English, $p^\*(w)$ is defined to be the node obtained by starting at $w$ and continuing upwards until we reach a node that has two or more children (or the root). In pre-processing, we'll compute the value of $p^\*(w)$ for each node $w$ and store it associated with $w$. This too can be computed in $O(n+m)$ time.

**Answering a query.** Now, here's how to answer the query *return any leaf that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$*:

* Case 1: Suppose $u$ is a child of $v$. Then, answering your query amounts to returning any leaf that is a descendant of $u$. This can be done in $O(1)$ time using the annotation on $u$.
* Case 2: Suppose $u$ is the parent of $v$, and $u$ has at least one other child. Then, look at any other child of $u$, call it $w$. Then, answering your query amounts to returning any leaf that is a descendant of $w$. This can be done in $O(1)$ time using the annotation on $w$.
* Case 3: Suppose $u$ is the parent of $v$, and $u$ has no other children. Then let $u'=p^\*(u)$ and let $w$ be any other child of $u'$ (not an ancestor of $v$). Then, answering your query amounts to returning any leaf that is a descendant of $w$. This can be done in $O(1)$ time using the annotation on $w$.

In all three cases, the answer to the query can be computed in $O(1)$ time.

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


title: IP addresses and Subdomains?

text:
# Question
Title: IP addresses and Subdomains?
If a school has an IP that's like 10.0.x.x, and a department in that school has it's own site that's an extension of the school's site, does that department's IP just change the last two numbers in the IP? Does the school have to purchase extra domain space? Could I have additional addresses established at my IP address, just by changing the last numbers? Am I completely wrong with my idea of IP numbers?

# Answer
> 2 votes
As we are talking about IPv4 addresses here, you have to consider two things:

* Usually, your Internet Service Provider (ISP) will assign you *one* IPv4 address. This can either be *changing* (the common case for private households) or *static*. However, there is usually *one* IP address at a time that you can be reached from the outside of your network.
* *Internally*, you can organize your network independent from those policy. For this purpose, some standard IP ranges like `192.168.*.*` and `10.*.*.*` are reserved to be used arbitrarily by the local network administrator.

Hence, **it is up to the network administrator** how the additional department is included in the school's local address space.

Generally, you want to talk of different loosely coupled networks in terms of *subnets*. To determine a certain subnet, you specify a *subnet mask*, which fixes the first $n$ bits of an IP address as "the network's address".

So, the admin would assign the additional department a "network address" of, e.g., `10.0.54.0/24`. This means, the first 24 bits of this IP identify the network and everything after the 24th bit can be assigned arbitrarily to the devices of that network. In this particular example, any device with an IP address between `10.0.54.1` and `10.0.54.254` would be logically seen as part of the network `10.0.54.0/24`.

Assuming that the whole school is connected to some kind of router (which uses NAT to "translate" the local IP addresses to the global IP address assigned by the ISP, roughly speaking), it is then **up to the router configuration** whether the department is reachable directly. This router will most likely run a *web server* or delegate http requests to a device of the network that runs a web server. Based on the configuration of this delegation or request processing, you can instruct the router to delegate any request to, e.g., `department.myschool.com` to the web server of the department and then you are fine.

However, you have to have a top level domain for this, even with a wildcard contract such that every request to `*.myschool.com` is forwarded to your school's router, that then can decide to forward requests to `department.myschool.com` accordingly. Another way to have this flexibility would to use different ports for different web servers in your local network. But this would burden anyone who is interested in your department's website to guess or somehow know the port your web server is listening to.

---
Tags: computer-networks
---


# Question
Title: Example for a non-trivial PCP verifier for an NP-complete problem
During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating

$\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$.

I understand the technical definition of a PCP verifier, so I know in principle what kind of algorithm has to exist for every NP problem: a randomised algorithm that checks $O(1)$ bits of the given certificate for the given input using $O(\log n)$ random bits, so that this algorithm is essentially a one-sided error Monte-Carlo verifier.

However, I have trouble imagining how such an algorithm can deal with an NP-complete problem. Short of reading the proof of the PCP theorem, are there concrete examples for such algorithms?

I skimmed the relevant sections of Computational Complexity: A Modern Approach by Arora and Barak (2009) but did not find any.

An example using a $\mathsf{PCP}(\\\_,\ll n)$ algorithm would be fine.

# Answer
Following up on a comment by sdcvvc I checked out example 11.7 in Computational Complexity: A Modern Approach by Arora and Barak (Draft of 2008). There, the authors describe a "PCP algorithm" for the problem *Graph Non-Isomorphism* (GNI):

> **Input:** Two graphs $G\_0$ and $G\_1$ with $n$ vertices each.
>
> **Output:** Accept if and only if $G\_0$ and $G\_1$ are not isomorph (write $G\_0 \not\equiv G\_1$).

We denote the certificate (they call it "proof") by $\pi$ and with $\pi(i)$ the $i$-th bit of $\pi$.

The algorithm $A$ proceeds as follows:

* Choose a bit $b \in \\{0,1\\}$ uniformly at random.
* Choose a permutation $\sigma \in S\_n$ (of the vertices of $G\_b$).
* Accept if $\pi(\langle\sigma(G\_b)\rangle) = b$, reject otherwise.

Here, $\langle \\\_ \rangle$ is some computable bijection from $\mathbb{N}^n$ to a suitable range $\[0..N\] \subseteq \mathbb{N}$. We assume that if the derefenced bit in $\pi$ does not exist, i.e. the certificate is too short, we reject.

**Claim:** By above algorithm, GNI is in $\operatorname{PCP}(n \log n, 1)$, i.e.

1. the algorithm uses $O(n \log n)$ random bits and queries $O(1)$ bits of $\pi$,
2. $(G\_0, G\_1) \in \mathrm{GNI}$ implies that there is some certificate $\pi$ so that $\Pr\[A(G\_0, G\_1, \pi) \text{ accepts}\] = 1$, and
3. $(G\_0, G\_1) \notin \mathrm{GNI}$ implies that $\Pr\[A(G\_0, G\_1, \pi) \text{ rejects}\] \geq \tfrac{1}{2}$ for *all* certificates $\pi \in \\{0,1\\}^\*$.

**Ad 1:** Clear from the algorithm by noting that uniform permutation sampling is possible with $\approx n \log n$ random bits¹.

**Ad 2:** Consider the certificate

$\qquad\displaystyle \pi(\langle H \rangle) = \begin{cases} 0 &, H \equiv G\_0, H \not\equiv G\_1 \\ 1 &, H \equiv G\_1, H \not\equiv G\_0 \\ \text{arbitrary} &, \text{ otherwise} \end{cases}$

where $H$ are all graphs with $n$ nodes. Since $G\_0 \not\equiv G\_1$ and $\sigma(G\_b) \equiv G\_b$, we have $\sigma(G\_b) \not\equiv G\_{1-b}$ for all $b$ and $\sigma$. The query to $\pi$ therefore always yields $b$ and thus always accept.

**Ad 3:** Let $\pi \in \\{0,1\\}^\*$ arbitrary and $H = \sigma(G\_b)$ the chosen query graph. If our query hits a non-existing bit of $\pi$ we reject by assumption, which is correct. Otherwise, we calculate

$\qquad\begin{align} \Pr\[\text{accept}\] &= \Pr\[b=0\] \cdot \frac{\\#\[\pi(H) = 0 \mid H \equiv G\_0\]}{\\#\[H \equiv G\_0\]} \+ \Pr\[b=1\] \cdot \frac{\\#\[\pi(H) = 1 \mid H \equiv G\_1\]}{\\#\[H \equiv G\_1\]} \\ &= \frac{1}{2} \cdot \left( \frac{\\#\[\pi(H) = 0 \mid H \equiv G\_0\]}{\\#\[H \equiv G\_0\]} + \frac{\\#\[\pi(H) = 1 \mid H \equiv G\_0\]}{\\#\[H \equiv G\_0\]} \right) \\ &= \frac{1}{2} \end{align}$ using that $H \equiv G\_1 \iff H \equiv G\_0$ in this case.

Thus, the claim is proven.

---

Some observations that helped me grasp these concepts better.

* The certificate $\pi$ can be arbitrarily long and arbitrarily complex. Note that "good" certificates for the above algorithm essentially solve the same problem as the algorithm (many times).
* But that does not imply that any decision problem can be solved in PCP style by "just providing the answer in the certificate". Condition 3 prevents any naive attempt of that kind.
* It is in general not possible to derive an efficient (randomised one-sided-error) algorithm that guesses the certificate (as is the case for NP-certificate verifiers).

---

1. Strictly speaking, this assumes that $n!=2^k$ (which of course almost never holds) since we have infinite worst-case runtime for other $n$. However, Arora/Barak seem to ignore this aspect.
> 8 votes

# Answer
Two problems that might help develop intuition:

1. Prove that $\mathsf{AM} \subseteq \mathsf{PCP}(\text{poly}(n),1)$. You are allowed to assume $\mathsf{NP} \subseteq \mathsf{PCP}(\text{poly}(n),1)$.
2. Prove that $\mathsf{PSPACE} \subseteq \mathsf{PCP}(\text{poly}(n),\text{poly}(n))$. Hint:

> Use IP = PSPACE

Trivia: The first exercise subsumes the PCP for GNI, while the second subsumes the PCP for permanent. Both results are subsumed by $\mathsf{NEXP} = \mathsf{PCP}(\text{poly}(n),1)$.
> 2 votes

---
Tags: algorithms, complexity-theory, np-complete, approximation, randomized-algorithms
---