# Question
Title: What's the correct definition of the $\Upsilon$ category of schedules?
I'm reading this article about game semantics and I'm a bit puzzled with the definition given for $\Upsilon$ in section $3.3$. There are some points that are either unintelligible or that don't make sense at all.

The definition provided is based on the concept of *schedule*:

> A schedule $e:\\{1, \ldots, n\\} \rightarrow {0, 1}$ is a sequence of $0$ and $1$s. We also define $|e| = n$, $|e|\_0$ is the number of $0$s in $e$ and $|e|\_1$ is the number of $1$s. The notation $e \upharpoonright m$ denotes the restriction of $e$ to its first $m$ terms.

(Where $e$ is actually a function, but we can view $e$ as the sequence $e(1)\cdot e(2)\cdots e(n)$.)

Now the definition of the category $\Upsilon$ is:

> * The objects are the natural numbers. We think of $p \in \Upsilon\_0$ as the totally ordered set $(p) = \\{1, \ldots, p\\}$. We write $(p)^+$ for the set of even elements and $(p)^-$ for the set of odd elements of $(p)$.
> * The morphism in $\Upsilon(p, q)$ are schedules $e$ such that $|e|\_0 = p$ and $|e|\_1 = q$.
>
> **A schedule $e: p \rightarrow q$ corresponds to obvious order preserving (collectively surjective) embeddings $l:(p) \rightarrow (p+q)$ and $r : (q) \rightarrow (p+q)$ and thus to order relations $l(x) \< r(y)$ from $(p)^+$ to $(q)^+$ and $r(y) \< l(x)$ from $(q)^-$ to $(p)^-$**
> * The identity in $\Upsilon(p, p)$ is the copy-cat function $c$ of length $2p$, such that $c(2k+1) \neq c(2k+2)$. **The induced orders are $\leq$ on $(p)^+$ and on $(p)^-$**
> * Let $e:p \rightarrow q$ and $f: q \rightarrow r$ be morphisms in $\Upsilon$, then their composition $e;f:p \rightarrow r$ is defined by taking the corresponding order relations , composing them as relations and **reconstructing the function**

Where I emphasized in bold the parts I don't understand. In particular:

* What's the meaning of *embedding* when he defined morphisms? I know what an embedding *functor* is, but this definition doesn't apply here.
* What does "$l(x) \< r(y)$ from $(p)^+$ to $(q)^+$" mean? Where do $x$ and $y$ come from? My *guess* is: $x \in (p)^+$ and $y \in (q)^+$. What are $l$ and $r$? My *guess* would be that $l$, given the index $x$ of a $0$ returns its index in $e$ and $r$ does the same for $1$s but then the $l(x) \< r(y)$ part doesn't make any sense to me.
* What's an *induced order*?
* What does *reconstructing a function* mean?

---

I hope my question is on-topic here. I didn't ask it on tcs because it doesn't look like a research level question to me.

---

**Edit**

Reading carefully the rest of the paper, later mentions that $l$ and $r$ are *injections*, so maybe for *embedding* he simply meant injection(?).

Assuming this, this is what I thought: the point about morphism means that $e$ could be seen to represent two injective functions $l:\\{1, \ldots, p\\} \rightarrow \\{1, \ldots, p+q\\}$ and $r:\\{1, \ldots, q\\} \rightarrow \\{1, \ldots, p+q\\}$ such that the union of their images is $\\{1, \ldots, p+q\\}$. These functions have the property that, for $x \in (p)^+, y \in (q)^+$, $l(x) \< r(y)$ and for $x \in (p)^-, y \in (q)^-, r(y) \< l(x)$ (although in the text this seems like a consequence of an "obvious order preserving ...". no idea what order he's talking about and how it's obvious.)

We can obtain these functions assigning the lowest values to even arguments for $l$, the next lower values for even arguments to $r$, then the next lower values to odd arguments for $r$ and finally the remaining values for $l$. (i.e. $r(2) = 1, r(4) = 2, \ldots, r(2k) = k$ then $l(1) = k+1, \ldots l(2t+1) = k+t+1$ etc.)

*However* such $l$ and $r$ are *not* unique, which *is* a problem in the rest of the paper since he later uses $l$ and $r$ in some definitions, which cannot be done if $l$ and $r$ aren't unique.

**Edit2**

Maybe the *embedding* means order-embedding. However even in this case I don't see how $e$ can be related with *one* obvious couple of order embeddings. I mean: the most obvious choice is to put $l(x)$ to be the index of the $x$th $0$ in $e$ and similarly for $r(y)$ and $1$s, but then the last statement in the description is wrong(take $e = 010$ we have that $r(1) = 2 \> l(1) = 1$ but we should have $r(y) \< l(x)$ for odd $x$ and $y$.

Is there any obvious way to define two embeddings $l$ and $r$ in a unique way?

# Answer
> 2 votes
I remember finding this bit very elliptic too. To me, this is clearly research-level, but anyway...

One point that you seem to have missed is that a schedule is defined as a map $e \colon \\{1,\ldots,n\\} \to \\{0,1\\}$ satisfying $e(1) = 1$ and $e(2k+1) = e(2k)$.

The intuition behind this is that we're considering *views*, in the game semantical sense. That is, we have an arrow arena, say $A \to B$, and two opponents, one on the left, say $L$, one on the right, say $R$, and the arrow arena lets us play against both of them at the same time. Only, $A$ and $B$ are \`polarised' games, i.e., players should take turns and the starting player is specified, and $R$ is to start in $B$, whereas we are to start in $A$. Finally, we are only allowed to change side when its our turn on both sides (this is called the *switching* condition) and the first move of all is to be played by $R$.

Schedules model \`shapes of plays' in such a setting. E.g., $0$'s and $1$'s stand for moves in $L$ and $R$, respectively. Hence, $e(1) = 1$ says that $R$ is to play first. Furthermore, $e(2k+1) = e(2k)$ says that all oour moves are immediately answered by the corresponding opponent.

Any schedule $p \to q$ is equivalently specified by the first point in $q$ after which we have played in $p$, then the first point after that in which we switched again to $q$, etc. The first relates an odd index in $q$ to an odd index in $p$, the second relates an even index in $p$ to an even one in $q$, etc, hence defining relations $R \colon (p)^+ \not\to (q)^+$ and $L \colon (q)^- \not\to (p)^-$.

Any such pair of relations comes from a schedule iff the union of $R$, $L$, and the underlying orders of $p$ and $q$ generates a total ordering on $p+q$. I haven't done the exercise of proving that such pairs $(R,L)$ are stable under composition...

Anyway, a graphical intuition is that instead of drawing schedules as (vertical) lists of $0$'s and $1$'s, you may draw any of them as *two* vertical lists of dots side by side ($0$'s to the left, $1$'s to the right!), plus arrows indicating when to switch from right to left and back.

The meaning of \`induced orders' are the obtained relations $R$ and $L$. So for copycat, they are relations $p^+ \not\to p^+$ and $p^- \not\to p^-$.

A doubt remains, to me at least, about their definition of copycat. I'd have said copycat induces the *discrete* order on both $(p)^+$ and $(p)^-$. Am I missing anything?

---
Tags: combinatorics, category-theory, game-semantics
---


# Question
Title: Is a non-perfect improvement and optimisation?
In real word problems, the influence of multiple not perfectly known factors results in using heuristics instead of mathemacial solutions that calculates a perfect value from only precisly defined input data. Consequently, any method that does not supply the mathematical maximum or minimum is not an optimisation but an improvement.

Somehow my opinion on this topic differs from the use of the term `optimisation` in many papers. Are the people just not precise in their language or is my understanding of the term wrong?

`Improvement` doesn't sound as facy as `optimisation`, but is there maybe some facy word that allows people to still be precise?

# Answer
Using mathematical nomeclature outside of the well-defined realm of mathematics often yields interesting problems. What for example do you mean by "proof" if you're not talking about logical deduction of a theorem from a set of axioms?

So when I talk about optimization I usually think about some more or less well defined problem, like "Given a set of factories and clients, how do I transport goods to clients using the minimal amount of money. I only have a limited amount of trucks and drivers, so there are some complicated constraints". The tricky part is judging which factors are important to my real world problem and modelling them using well-defined mathematical objects. This transition from real world to mathworld is usually hard and requires several attempts. The result of the process is the *optimization problem* that we want to solve using mathematical methods. But note that it's only our approximation of the real world and we left out lots of things that we deem irrelevant!

Most real world problems are of course difficult and any model that can give reasonable results is at least NP-hard to solve optimally. So we use heuristics. I still think of this as an optimization process, since I do improve something until I reach some kind of solution. It might not be the global optimum, or even a local optimum, but it's the best I can do. Since my original formalization of the problem already left out lots of things that might or might not have influence on the solution, this additional layer of suboptimality does not matter too much to me.
> 4 votes

---
Tags: terminology, optimization, approximation, applied-theory, approximation-algorithms
---


title: Deciding the class of certain languages

text:
# Question
Title: Deciding the class of certain languages
I am preparing for my exam in Formal languages and Automata theory and I'm looking at some old exam questions right now. I need help with the following question:

> For each of the following languages answer whether it is regular, context-free but not regular, or not context-free. A brief, informal explanation is sufficient.
>
> $$ L\_3 = \left\\{ w \in \\{a,b,c,d\\}^\* \Bigg| \begin{array}{l} \text{\\(w\\) does not have a substring \\(aba\\),} \\ \text{each \\(a\\) in \\(w\\) is immediately followed by \\(b\\),} \\ \text{and \\(\\#c(w)\\) is odd} \end{array} \right\\} $$ $$ \begin{align} L\_4 &= \\{ a^ib^jc^ka^ib^l \mid j \gt l \text{ and } i,l,k \gt 0 \\} \\ L\_5 & \text{ is the image of \\(L\_4\\) under the homomorphism } h:\\{a,b,c,d\\}^\* \to \\{0,1,2\\}^\* \\ & \text{ such that } h(a) = h(b) = 10 \text{ and } h(c) = 210 \text{ and } h(d) = \epsilon \\ L\_6 & \text{ is the image of \\(L\_4\\) under the homomorphism } h:\\{a,b,c,d\\}^\* \to \\{0,1,2\\}^\* \\ & \text{ such that } h(a) = h(b) = 210 \text{ and } h(c) = h(d) = \epsilon \\ \end{align} $$

Here is my attempt:

$L\_3$ is regular. It's the intersection between 3 regular languages. Regular languages are closed under intersection, so the resulting language is regular. The language where $w$ does not have a substring $aba$ is just the complement of the language $aba$, regular languages are closed under complement, so the resulting language is regular. The language with an odd number of $c$ is regular. Hence the resulting language when taking the intersection between these languages is regular.

$L\_4$ is not context-free. When reading the first $a$'s we will push the $a$'s onto the stack. Then we will read the first $b$'s and push them onto the stack. Then we will read the $c$'s. When we now read a second group of $a$'s, we will not be able to compare the number with the first $a$'s, because $b$'s are on the top of the stack and if we pop them then we will not be able to compare the number $b$'s in the beginning and the end. Hence, $L\_4$ is not context-free.

$L\_5$ is context-free but not regular. The language in question looks like this: $$ 10^{i+j} 210^k10^{i+l} \text{ where } j \gt l \text{ and } i,l, k \gt 0 $$ A grammar can be constructed which generates at least one more $10$ in the beginning of the string than $10$ after $210$.

$L\_6$ is regular because it's given by the regular expression: $$ 210^{2i + j + l} \text{ where } 2i+j+l \text{ is any number } \gt 0$$

Is this correct? Note that informal explanations is sufficient in the answer and that no grammars has to be given.

# Answer
The answers are correct, but when proving that a language is not regular, or not context-free, it is not enough to show that one attempt does not work. You have to use tools like pumping lemma. For context-free languages, there is a version of pumping lemma which should work here: http://en.wikipedia.org/wiki/Pumping\_lemma\_for\_context-free\_languages

Also it's a detail, but in your last argument, $2i+j+l$ is not any number $\>0$, it is at least $5$, since $j\>l$ and $i,l,k\>0$. So your language is $\\{(210)^n : n\geq 5\\}$, which is indeed regular.
> 2 votes

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


# Question
Title: Compiler backend generated from declarative description of the architecture
Is it possible, given a declarative description of an architecture's register layout and instruction semantics and machine code encodings, to autogenerate a compiler back-end?

If so, has anyone ever done this?

# Answer
> 3 votes
João Dias; Norman Ramsey: "Automatically Generating Back Ends Using Declarative Machine Descriptions", *Proc. ACM Symp. Principles of Prog. Lang.*, (POPL-37):403-416, 2010.

I think this goes a bit farther than you asked for, because they're actually looking for *good* code sequences. For something a little more basic you could go back to some of Norm Ramsey's earlier work, like: Norman Ramsey; Mary F. Fernández: "Specifying Representations of Machine Instructions", *ACM T. Prog. Lang. and Sys.*, 19(3):492–524, May 1997.

There's a long line of research on trying to automatically generate back ends from simpler descriptions. Look for papers by Christopher W Fraser, David R Hanson and Todd A Proebsting.

---
Tags: compilers
---


# Question
Title: Give a recursive function $r$ on $A$ that reverses a string
I really need help with this task here. Im stuck at it and I really would appreciate your help

Here is the task:

> Give a recursive function $r$ on $A$ that reverses a string. For instance, $r(logikk) = kkigol$ and $r(moro) = orom$. (given that $A$ the amount of letters in the Norwegian alphabet which has 29 letters.). Define the function in such a way that it is correctly regardless of what $A$ are.

Also $logikk$ means $logic$ in norwegian, and $moro$ means $fun$ in norwegian in case you're wondering.

**Edit:**

I tried to solve one of the recursive functions, $r(logikk)$, but i'm not sure if all of it is correct:

> $\Lambda =$ The empty string
>
> $r(\Lambda) =$ $\Lambda$, $r(k) = k$, $r(k) = k$, $r(i) = i$, $r(g) = g$, $r(o) = o$, $r(l) = l$
>
> For any word $w$ and letter $a$, $r(wa) = wa$

Can someone please check if this is correct for $r(logikk)$ I feel like i'm missing something but i'm not sure what.

# Answer
> 2 votes
A recursive function requires base cases and recursive rules. Depending on how your system works, your base cases might include:

* $r(\lambda) = \lambda$
* $r(\sigma) = \sigma$ for $\sigma \in \Sigma$
* etc.

You then need a general rule for more complicated cases. You're on the right track; you need a rule that takes something of the form $\sigma w$, where $\sigma \in \Sigma$ is a single letter and $w \in \Sigma^\*$ is some arbitrary string, and produces the correct output. You will likely find, and should try to prove, that a rule like the following works:

* $r(\sigma w) = w \sigma$

Fits the bill. Putting it all together, in pseudocode, you should arrive at something roughly like the following:

```
Reverse(string[1...n])
1. if n = 0 then return the empty string
2. else if n = 1 then return string[1]
3. else return the concatenation of Reverse(string[2...n]) with string[1]

```

# Answer
> 1 votes
Hint: Distinguish between two cases: the input is a single letter $\alpha$, and the input is a word $w = \alpha x$ (where $\alpha$ is a letter). In the first case, $f(\alpha) = \alpha$. What can you say in the second case? (For example, consider $w = logikk$, $\alpha = l$, $x = ogikk$.)

---
Tags: recursion, functional-programming
---


# Question
Title: Proof that there is unambigous grammar for every regular language
How can I prove, or where can I find proof that for every regular language there is unambigous grammar?

# Answer
Something like this might work. First, note that every regular language is accepted by some minimal DFA. Call such a DFA $M$. Next, describe how you could construct a right-regular grammar that accepts the same language as $M$. Take as your set of nonterminal symbols the set $Q$ of states of $M$. Form the set of productions as follows: the smallest set of productions such that if $M$ has a transition from $q\_1$ to $q\_2$ on $\sigma$, then there is a production $q\_1 \rightarrow \sigma q\_2$, and also a production $q\_1 \rightarrow \sigma$ if $q\_2$ is an accepting state. (You'll also need to add the production $q\_0 \rightarrow \epsilon$ if the empty string is in the language).

Now, if this grammar is ambiguous, there are two different derivations for some string. This would imply that, at some point, more than one transition was available in the minimal DFA (since each production corresponds to some transition). This is a contradiction, since there cannot be more than one valid transition at any time while a DFA processes input.

Basically, while you're very right that right-regular grammars can be ambiguous, you can actually construct a specific right-regular grammar that must be unambiguous. All you have to do is describe the method of construction and produce a valid argument why it's right-regular and why it can't be ambiguous.
> 3 votes

# Answer
Hint: Use a right-regular grammar. This is a kind of grammar which has rules of the following types: $A \to aB$ and $A \to \epsilon$.
> 0 votes

---
Tags: proof-techniques, ambiguity
---


# Question
Title: experimental analysis of running times in extendable table
I was given the following homework question:

> Implement an extendable table using arrays that can increase in size as elements are added. Perform an experimental analysis of each of the running times for performing a sequence of n add methods, assuming the array size is increased from N to the following possible values:
>
> * 2N
> * N + ceiling(√N)
> * N + ceiling(log N)
> * N + 100

I'm just a little confused about what this question is asking, and was hoping for some help/clarification. The way I understand it, you could implement something like this in Python with a two-dimensional array (the "extendable table"), and then append varying numbers of values for each scenario. Am I understanding the implementation correctly?

Then, I'm also a bit unclear on what number of values you'd be appending. Would you literally first test it with say, 16 values, then 32 (2N), then 20 (ceiling(√N)), etc? Or is it more complex than that? Any help is appreciated!

# Answer
An extendable array *isn't* a two-dimensional array (I don't know what's an extendible *table*). The idea is that you start with an array of a fixed size, and each time you are trying to insert an element into the array but it's full, you increase the size from $N$ (its current size) to $f(N)$ (its subsequent size, until it needs to be enlarged again). That means that you allocate new memory ($f(N)$ items), copy the old array into the new place, and then free the old memory. When you have added $f(N)-N-1$ more elements, a subsequent insertion would require enlarging the array to size $f(f(N))$, and so on. The question is what is the best choice for the function $f$.

Experimentally, you can try different functions $f$. For each such suggestion $f$ (and the *same* initial size of the array, say something like 20 or 100, you decide), plot $n$ against the time it takes to add $n$ elements (what elements you add isn't important; you could just add zeroes), averaged over several trials. I'll let you decide how exactly to do that, but you probably want several different values of $n$, and $n$ as large as roughly a million or so (you decide exactly how large). You can then find which function is better than others. I suggest you use C rather than python in your experiments.
> 0 votes

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


# Question
Title: Is the per-vertex error over a PageRank iteration monotonically decreasing?
It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge.

However, is the same true on a per-vertex basis? I.e., from iteration t to iteration t+1, is the squared error of a vertex guaranteed to always decrease as it moves closer to its PageRank value? Or is it possible that the vertex squared error would ever increase?

This also seems to me to have some broader relationship with power iterations in general? Some explanation or proof with the answer would be appreciated.

# Answer
No. Consider the case of an isolated component with a central vertex v that is pointed to by vertices x\_1, ...., x\_k. The initial value at v is 1/n, and the final value should be roughly k * the restart probability/n. But the value at v in the second round is roughly k/n. If the restart probability is significantly less than 1/k, then the value got further from the ultimate value.
> 3 votes

---
Tags: graphs, algorithm-analysis, error-estimation
---


title: Multivalued, partial evaluation

text:
# Question
Title: Multivalued, partial evaluation
Everybody says that *Valuation* is a **truth value** assignment to **all** variables in the formula.

1. How do you call the valuation when some (neither single yet nor all) variables are assigned a value?
2. `Truth value` implies that variables are binary. How do you call the multivalued case?
3. I know that Haskel uses the term "partial application". If "partial application" is supplied with optimization, they call it "partial evaluation". I am not sure whether boolean valuation falls into the `application` or `evaluation` or second category?

**ps, Dec 2013**

1. Is it right that single variable assignment is called **Restrict** operation? I read `Restrict(Function F, variable v, constant k)` is defined as "Shannon cofactor of $F$ w.r.t. $v=k$" in Berkly lectures.

# Answer
Here's what I'd use:

1. partial valuation
2. value
3. "partial evaluation" means something different; for instance, if you have the expression `(3+x)*y` and you learn that `x=5`, transforming it to `8*y` would be an instance of partial evaluation. Partial evaluation is a technique; it is not a special kind of a valuation.
> 2 votes

---
Tags: terminology, logic
---


# Question
Title: Is there a theory of exception hierarchies?
I'm familiar with a dozen of programming languages which have exceptions in some way, yet I came to witness two "pathological" tendencies.

1. There doesn't seem to be a common pattern or hierarchy of exceptions. Every language basically rolls its own version, and if the exceptions make it into the standard, then the kinds of exceptions that one finds in the standard would be rather arbitrary (mostly those which were implemented while creating language tools, such as reading source code from string or an exception to invoke debugger, or the one which happens when the file cannot be found etc.)
2. Exceptions defined by the language are very rarely reused by user programs. There would be usually one or two popular exceptions ("not implement" for example). Though most times programmers will create their own exceptions. (Compare this to, for example, creating new numeric types or new collection types).

This looks like a terrible omission to me. How comes no one knows what kinds of errors will be needed in user programs? I was hoping for there to be a kind of nice hierarchy, similar to numeric types, collections, object system etc.

Worse yet, Goolge and Wikipedia provide very little help on the subject. So far I've only found a paper on functional exception which opens in a passage:

> This paper argues that lazy functional programming not only makes built-in exception handling mechanism unnecessary, but provides a powerful tool for developing and transforming programs that use exceptions

*(A Functional Theory of Exceptions, Mike Spivey, 1988)*

But I think that exceptions are good. I don't want to transform programs that use exceptions, on the contrary, I want to make the use of exceptions less chaotic.

# The question:

Is there a theory of exceptions? If so, what is it called? What are, if any, the cornerstone works outlining the basis of it?

# Answer
> 8 votes
There's a large number of publications on exceptions, with quite a few theoretical investigations. Here is an unstructured and far from complete list with some examples. Sorry, I don't have time at the moment for a more focussed reply.

* B. Randell, System Structure for Software Fault Tolerance.
* J. B. Goodenough. Exception handling: Issues and a proposed notation.
* J. B. Goodenough. Structured exception handling.
* B. G. Ryder, M. L. Soffa, Influences on the Design of Exception Handling.
* D. Teller, A. Spiwack, T. Varoquaux, Catch me if you can: Towards type-safe, hierarchical, lightweight, polymorphic and efficient error management in OCaml.
* X. Leroy, F. Pessaux, Type-based analysis of uncaught exceptions.
* R. Miller, A. Tripathi, Issues with Exception Handling in Object-Oriented Systems.
* S. Drew, K. J. Gough, J. Ledermann, Implementing Zero-Overhead Exception Handling.
* B. Stroustrup, Exception Safety: Concepts and Techniques.
* D. Malayeri, J. Aldrich, Practical Exception Specifications.
* H. Nakano, A Constructive Formalization of the Catch and Throw Mechanism.
* A. Nanevski, A Modal Calculus for Exception Handling.
* P. de Groote, A Simple Calculus of Exception Handling.
* H. Thielecke, On Exceptions and Continuations in Presence of State.
* J. G. Riecke, H. Thielecke, Typed Exceptions and Continuations Cannot Macro-Express Each Other.
* M. van Dooren, E. Steegmans, Combining the Robustness of Checked Exceptions with the Flexibility of Unchecked Exceptions using Anchored Exception Declarations.
* J. A. Vaughan, A logical interpretation of Java-style exceptions.
* S. Marlow, S. Peyton Jones, A. Moran, Asynchronous Exceptions in Haskell.
* B. Jacobs, F. Piessens, Failboxes: Provably Safe Exception Handling.

# Answer
> 6 votes
I don't know whether or not there is a theory, but there may be an emerging pragmatic experimental science.

The best source I can think of is Bjarne Stroustrup, The Design and Evolution of C++, Addison-Wesley, 1994. If I remember correctly (it's a very good book and people keep borrowing it from me and not returning it, so I don't have a copy at the moment) there's a chapter about exceptions. The C++ committee under Stroustrup required a lot of empirical evidence that a proposed feature was necessary before they were willing to add it to the language definition. The Wikipedia page about exceptions has the following quote from that book:

> At the Palo Alto \[C++ standardization\] meeting in November 1991, we heard a brilliant summary of the arguments for termination semantics backed with both personal experience and data from Jim Mitchell (from Sun, formerly from Xerox PARC). Jim had used exception handling in half a dozen languages over a period of 20 years and was an early proponent of resumption semantics as one of the main designers and implementers of Xerox's Cedar/Mesa system. His message was termination is preferred over resumption; this is not a matter of opinion but a matter of years of experience. Resumption is seductive, but not valid. He backed this statement with experience from several operating systems. The key example was Cedar/Mesa: It was written by people who liked and used resumption, but after ten years of use, there was only one use of resumption left in the half million line system -- and that was a context inquiry. Because resumption wasn't actually necessary for such a context inquiry, they removed it and found a significant speed increase in that part of the system. In each and every case where resumption had been used it had -- over the ten years -- become a problem and a more appropriate design had replaced it. Basically, every use of resumption had represented a failure to keep separate levels of abstraction disjoint.

In C++ the real win is RAII, which makes it much easier to handle resource deallocation during errors. (It doesn't do away with the need for `throw` and `try`-`catch`, but it means you don't need `finally`.)

I think the thing that convinced them they needed exceptions is generic containers: the container writer knows nothing about the kinds of errors that the contained objects might need to return (much less how to handle them), but the code that inserted those objects into the container must know something about what those objects' interface is. But since we know nothing about what kinds of errors the contained objects can throw, we can't standardize on exception types. (Contrapositively: if we could standardize exception types then we wouldn't need exceptions.)

The other thing that people seem to have learned over the years is that exception specifications are hard to put into a language correctly. See for example this: http://www.gotw.ca/publications/mill22.htm, or this: http://www.gotw.ca/gotw/082.htm. (And it's not just C++, Java programmers also have lengthy arguments about their experiences with checked versus unchecked exceptions.)

A little on the history of exceptions. The classic paper is: John B. Goodenough:"Exception handling: issues and a proposed notation," *Commun. ACM* 18(12):683-696, 1975. But exceptions were known before that. Mesa had them in about 1974, and PL/I may have had them too. Ada had an exception mechanism before 1980. I believe that C++'s exceptions were most influenced by the experience with Barbara Liskov's CLU programming language from about 1976. Barbara Liskov: "A history of CLU," in *History of programming languages---II*, Thomas J. Bergin, Jr. and Richard G. Gibson, Jr. (Eds.). pp. 471-510, ACM, 1996.

# Answer
> 3 votes
Let me just point out that exceptions are a case of *computational effect*. Other computational effects are mutable state, I/O, non-determinism, continuations, and many others. So your question could be asked more generally: how do we form hierarchies of computational effects, how do we organize them, and why do we have the ones we have, and not others, etc.

---
Tags: terminology, programming-languages, api-design
---


# Question
Title: Where in the Chomsky Hierarchy are Regular Expressions as a language?
I'm referring to regular expressions as language: \begin{equation\*} \Sigma = \\{ \`\`a", \`\`b", \`\`(", \`\`)", \`\`\*", ... \\} \end{equation\*} and \begin{equation\*} L = \Sigma^\* \text{, which form a legal regular expression} \end{equation\*} I am not referring to their computational power. I did some research, but wasn't able to find anything relevant. Intuitively, I would imagine they're context-free, but am not sure how to attempt a proof.

I am trying to use this as a lemma, so a reference, or recommendation for how to attempt a proof would be extremely helpful.

# Answer
Are we talking regular expressions as in only union, concatenation and star?

Consider the following grammar:

$R -\> a | b | c$

$R -\> R+R$

$R -\> RR$

$R -\> R^\*$

$R -\> (R)$

This captures all regular expressions. So if we're only talking in the Chomsky hierarchy, then it's clearly context free. If you allow parentheses, it's not regular, since well-nested parentheses are known to not be regular. If you want a proof, do a homomorphism from the language of REs to the language of well-nested parentheses.

I don't know where they fit in terms of more detailed classification (i.e. $LL(1)$, $LR(0)$ etc.).

You could probably find something about this if you searched for "parsing regular expressions."
> 3 votes

---
Tags: formal-languages, reference-request, regular-languages
---


title: Solving $T(n)=4T(n/2)+n^2$

text:
# Question
Title: Solving $T(n)=4T(n/2)+n^2$
I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T(n/2)+n^2$$ My guess is $T(n)$ is $\Theta(n\log n)$ (and I am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that $T(n)\le cn^2\log n$ but that did not work, I got $T(n)\le cn^2\log n+n^2$.

I then tried to show that, if $T(n)\le c\_1 n^2\log n-c\_2 n^2$, then it is also $\mathcal O(n^2\log n)$, but that also did not work and I got $T(n)\le c\_1n^2\log(n/2)-c\_2 n^2+n^2$.

What trick can I use to show that? Thanks.

# Answer
You must subtract a *lower order term* in order to strengthen your inductive hypothesis: try

$T(n) \leq c\_1 n^2 \lg n- c\_2 n$ and you will be able to show by substitution that $T(n) = O(n^2 \lg n)$ for appropriate values of the constants ($c\_2 \> 1$ and $c\_1$ big enough to correctly handle the initial conditions).
> 6 votes

# Answer
I always use following approach: Try to avoid master theorem as a recursion solution gives you more insight to the structure of the problem:
> 3 votes

# Answer
That's a recurrence of the form: $T(n)=aT(n/b)+f(n)$. In your case $a=4$, $b=2$, and $f(n)=n^2$. This is case 2 of the master theorem. It follows that $T(n)=\Theta(n^2\log n)$.
> 1 votes

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


# Question
Title: Prove that {0^{n^3} | n≥0} is not context free
I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L = \\{0^{n^3} \mid n\in\mathbb{N}\\}$ is context-free or not.

Based on my intuition, it won't be. There is no pattern of $0$'s that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i \ge 0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.

# Answer
Gilles suggests a sophisticated method for solving this exercise, which is also the "proper" method; we will say more about it below. But let's start with applying the pumping lemma. The pumping lemma states that if $L$ is context-free then there exists some integer $n$ such that all words $w \in L$ of length at least $n$ can be written in the form $w = uvxyz$ with $|vxy| \leq n$ and $|vy| \> 0$ (i.e. not both $v,y$ are empty), such that $uv^ixy^iz \in L$ for all $i \geq 0$.

Let's see what this means in your case. Suppose $L$ were context-free, and let $n$ be the integer given by the pumping lemma. Take some $m$ satisfying $m^3 \geq n$. Since $0^{m^3} \in L$ and the word has length at least $n$, we can write $0^{m^3} = uvxyz$ such that $|vy| \> 0$ and $|vxy| \leq n$, and furthermore $uv^ixy^iz \in L$ for all $i \geq 0$. So $vy = 0^t$ for some $1 \leq t \leq n$, and for all $i \geq 0$, $0^{m^3-t+it} \in L$, that is, for all $i \geq 0$, $m^3 + (i-1) t$ is a cube. Your mission is to somehow reach a contradiction from this data.

---

Now for Gilles' proof. We can consider the language $L$ over the unary alphabet $\Sigma = \\{0\\}$. Parikh's theorem states that $L$ is context-free iff it is regular. The proof is not difficult: if $L$ is regular then it is context-free, and in the other direction you take a grammar for $L$ and massage it into an equivalent right-regular grammar; the idea is that $xy = yx$ if $x,y \in 0^\*$.

The next step is to find a criterion for when a language $L\_A = \\{ 0^n : n \in A \\}$ is regular. By considering a DFA for $L\_A$, it is not hard to show that $L\_A$ is regular iff $A$ is eventually periodic, that is, for some $a \geq 0$ and $b \geq 1$ it is the case that $x \in A$ iff $x + b \in A$ for $x \geq a$. This is not the case for the set of cubes, since the gap between adjacent cubes tends to infinity. We conclude that $L$ isn't regular nor context-free.
> 1 votes

---
Tags: context-free, pumping-lemma, pushdown-automata
---


title: Is this pumping lemma proof correct?

text:
# Question
Title: Is this pumping lemma proof correct?
$$ L = \\{a^ib^jc^k \mid i,j,k \> 0 \text{ and } i+k\>j\\} $$

I say it's not regular. Proof by pumping lemma: Find a string $xy^iz$ that is not in $L$ (respecting the constraints). Let $w=x^py^pz^p$.

Let $i=2$. $x^p(y^py^p)z^p$ is not in $L$.

Thus $L$ is not regular.

Is this proof correct?

# Answer
> 1 votes
The proof is not correct nor complete. You have to show that for every possible splitting of the string to be pumped, where the constraints of the lemma hold, the pumped string does not belong to the language.

You have only showed for one case that the string does not belong to the language and hence that the language is not regular.

But what about this case:

$$ z = x^py^pz^p, take \ i = 0 \ , uv = x^p, \ then \ z = uv^0w \ does \ not \ belong \ to \ the \ language, \ the \ condition \ i+ k \> j \ is \ violated $$

You have to show that for every possible splitting of the string to be pumped, where the constraints hold, for some i, the string does not belong to the language.

# Answer
> 1 votes
Here is a different proof. Suppose $L$ was context-free. Then so would be $L\_1 = \\{ a^i b^j : i \> j \> 0 \\}$, hence so would be $L\_2 = L\_1 b + a^\* ab + a^\* = \\{ a^i b^j : i \geq j \geq 0 \\}$. Reversing $L\_2$ and switching $a$ and $b$, we would also have $L\_3 = \\{ a^i b^j : j \geq i \geq 0 \\}$ regular. So the intersection $L\_2 \cap L\_3 = \\{ a^n b^n : n \geq 0 \\}$ would be regular, which was probably shown in class to be false.

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Removing constant symbols from language to prove irregularity
I'm confused about a solution I saw about the following language not being regular:\begin{equation\*} L=\\{0^n ~1 ~2^n : n \>0\\} \end{equation\*} The example solution said that $L$ was "the same as":\begin{equation\*} L'=\\{0^n1^n : n \> 0 \\} \end{equation\*} so it wasn't regular. I understand why $L'$ isn't regular, but I don't understand how $L$ is the same as $L'$. How can you eliminate that middle symbol?

# Answer
> 4 votes
The language $L'$ is the "same" as $L$ (in fact, it's an asymmetric relation) in two steps. If $L$ were regular, then so would be $L'' = \\{0^n 2^n : n \> 0 \\}$ (take a DFA for $L$ and replace $1$ edges with $\epsilon$ edges). In its turn, $L''$ is the same as $L'$, up to change of symbols.

---
Tags: regular-languages
---


title: Universal Hashing in Practice

text:
# Question
Title: Universal Hashing in Practice
A family $H$ of hash functions $h: U \rightarrow \\{0,\ldots,M-1\\}$ is *universal* if $$\forall x,y \in U, x \neq y \Rightarrow \Pr\_{h \in H}\[h(x) = h(y)\] \leq \frac{1}{M}$$ You can find more about universal hashing this wikipedia article.

The concept of universal hashing is now a standard part of undergraduate data structure courses. It would be nice to be able to motivate students about the importance of universal hashing in industrial applications. So my question is:

> Are constructions of universal family of hash functions important in practice? If the answer is yes, would you please share some interesting industrial applications that you've seen?

# Answer
> 4 votes
Universal hashing (or near-universal) is a key ingredient in defending against algorithmic complexity attacks that engineer hash table collisions from user input.

See Scott A. Crosby and Dan S. Wallach's "Denial of Service via Algorithmic Complexity Attacks".

---
Tags: data-structures, education, hash-tables, applied-theory
---


# Question
Title: What does "deterministic" mean in the context of memory management?
At the time of writing, Wikipedia describes determinism as:

*"a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states"*

That aligns with my interpretation of determinism as a natural scientist.

If a program contains a benign race condition and its control flow varies depending upon the outcome of the race, is it deterministic? I would say not. However, many people describe thread-safe reference counting, such as `shared_ptr` in C++, as deterministic even though threads race to decrement the reference count to zero and the winner is responsible for executing the destructor.

The Wikipedia page about garbage collection lists determinism as an advantage of reference counting compared to tracing collection and determinism is also referred to here. On the other hand, people have blogged rants explaining why this is wrong.

So what does "reference counting is deterministic" mean, if anything?

# Answer
> 3 votes
> So what does "reference counting is deterministic" mean, if anything?

It means it is deterministic in the absence of multiple threads. Threads almost always ruin this sort of determinism, with or without a race condition, memory collection or whatnot: in one run, thread A, can be scheduled first a bit, then another thread, B gets scheduled a bit; in a second run, the OS can schedule the threads to run in the opposite order, thus almost all threaded programs inherently lose this determinism.

Therefore "race condition" and "threads" usually put a procedure out of the scope of this use of this meaning of determinism.

# Answer
> 2 votes
Determinism is an absolute, objective concept — either a process always produces the same result, or it doesn't.

Well, no, it's not so simple. When people say that something is deterministic, they're often leaving out a precise specification of just what it means for the process to be executed **in the same conditions**. A deterministic process always produces the same result for a defined set of initial conditions. It matters what you consider part of the process and what you consider part of the initial conditions.

Concurrency is an extreme case of non-determinism. In pretty much any model of concurrency, scheduling introduces a source of non-determinism, and the most we can expect is that one thread or node behaves deterministically, if the behavior of the rest of the system is constant from its point of view. Any timing difference causes the thread to observe the rest of the system in a different way, which allows it to behave differently.

Input/output can cause a program to behave differently. Again, very much like a thread in a concurrent system, a program that performs I/O is only expected to behave deterministically if its interactions with the rest of the world are fixed. A sequential program that doesn't perform any I/O (including things like calls to random number generator) is expected to be deterministic. Its behavior is thus fully predictable and reproducible. Let's call such a program a pure program.

What this means for memory management is that a pure program is deterministic, no matter what memory allocation strategy is used.

Now as hinted above this statement needs to be qualified. What assumptions are hidden here?

An important assumption is of course that **the memory allocation strategy is fixed**, and non-randomized. A different memory allocation strategy could obviously lead to different behavior, including the memory being full or not full at different times in the program's execution.

Another assumption is that we're talking about a **complete program**, starting from a known initial state. As far as memory management is concerned, we're running the program starting with a fixed heap configuration.

But **what if we were talking about a program fragment?** We tend to like our notions about programs to be compositional, because we're forever building bigger programs from components. Depending on where and how a given program fragment is executed, it may be started from different heap configurations.

Garbage collection affects the heap globally. If a collection happens during the execution of the program fragment, it may also affect storage used by the rest of the program. Thus garbage collection exhibits a strong dependency on the program as a whole. An object that stops being used may or may not be collected because a collection may or may not be triggered at a particular point, or because the minor heap may fill up at a different time for a generational collector, etc.

Reference counting is *more deterministic* than garbage collection because there are fewer dependencies to the rest of the program. An object used solely by the program fragment is freed when its reference count reaches 0, and this does not depend on the what the rest of the program had been doing.

Reference counting, like most memory management strategies, is not fully deterministic from this point of view. The state of the heap when the fragment starts matters because of fragmentation. Even for a given amount of free memory when the fragment starts, a difference in size and layout of the free areas may lead to the program running out of memory, or not. The amount of time spent managing the data structures of the memory allocator may also vary depending on the shape of the free areas in the heap.

This is the case for any memory allocation strategy, including fully manual management, except for strategies guaranteed not to run out of memory (such as fully static allocation).

Just about any memory allocation strategy is non-deterministic in the sense that the behavior of a program fragment is affected by the surrounding program — both in terms of whether a given allocation will succeed (and at which address), and in terms of how much time is spent on memory management at any given point. The difference between reference counting and garbage collection is not one of nature but one of degree. Reference counting is **more deterministic** than garbage collection (under typical approaches). And that's without getting into concurrency, where pretty much anything is non-deterministic.

Arguing whether a strategy is “deterministic” without enough context to precisely specify what is meant is a matter of semantics. In the colloquial sense of “arguing about words and forgetting about their meaning”, not in the technical sense of “the study of the meaning of programs”.

# Answer
> 1 votes
As the other poster said, determinism is the idea that given initial conditions A and B a process will produce output C where the time used is part of the definition of C. Because of the evolution of computers many people have losses sight of the point at which the pre-conditions A and B no longer apply to a program but to the entire computer. Modern general purpose computers can never be deterministic due to entropy generate by the interaction of the clock with the kernel schedular and other issues. Hard realtime systems use dedicated chips (think car breaks) or FPGAs (think high speed trading) to ensure determinism.

OK regarding memory management, the idea of determinism can and should be broadened to a soft realtime concern. We want memory reclamation to happen within a known, bounded time. We also do not want the upper limit of that time to be too long (as determined during requirements gathering) and so make out program's non-function specification have an unacceptable upper time limit or jitter.

Shared\_ptr is a poor choice because of its low over all performance and because of its large jitter. Thus (I wrote the rant) I don't think it should ever be used unless there is absolutely no other choice. Also, it does not work for memory management due to cycles. In general it is bad (ranting again).

By comparison, on most modern machines, assuming our process does not loose its quantum during reclamation, automatic (stack) memory is deterministic enough to be considered deterministic in the real world.

In financial low latency systems, any instruction which locks the memory (as shared\_ptr does) must be avoided. Funnily enough, that is something I am currently involved with.

All the best - AJ

---
Tags: nondeterminism, memory-management
---


# Question
Title: How many virtual machines run inside MS Windows?
In my Computer Systems (first year) module as part of my EE degree I'm studying virtual machines, memory management, hardware abstraction etc. I have come across the information that the OS creates and uses a few virtual machines to provide hardware and I/O abstraction.

I assume that there are multiple VMs doing different tasks, but how are they organised?

Are they one VM per task, e.g. one for disk I/O and the filesystem, one for human interface devices, etc; or are they all general purpose and are one VM per process?

Many thanks, Ben Adamson

# Answer
The NT kernel does have sub-systems or did for DOS, Win32, POSIX, and OS/2. You might consider them to be a VM layer in that they are instantiated per process and provides a compatible binary API to the process so that it may run. Each of these sub-systems only maps the binary API for the process to the API of the kernel and as such they don't do much other than that. State pertaining to a sub-system is kept in the process's context.

See chapter 5 in *Inside Windows NT* (Helen Custer, 1993) for more.
> 0 votes

---
Tags: operating-systems
---


title: sock matching algorithm

text:
# Question
Title: sock matching algorithm
There are $n$ pairs of socks, all different. They all went out of the dryer, so there are now $2n$ socks scattered around. Given two socks, the only operation I can do is to decide whether they are identical (- belong to the same pair) or different (- belong to different pairs). What is the best way to sort the socks in matching pairs?

The obvious algorithm is: grab a sock, scan the pile for its matching sock, and put that pair aside. This algorithm requires time $O(n^2)$.

I Found a related question, On the complexity of sock-matching from about 10 years ago, which also describes an $O(n^2)$ algorithm.

If each sock has a numeric ID, or another ordinal property, such as: wavelength of color, then the entire set of socks can be sorted by that ordinal property in time $O(n log n)$, and then the pairs can just be collected with an $O(n)$ scan. But, in this question I assume that there is no order on the socks - we can only tell whether two socks are identical or different.

In a similar question in StackOverflow (How to pair socks from a pile efficiently?), the accepted answer suggests to use a hash, but again, this assumes that each sock can be represented by a set of properties such as color, pattern, etc., so that each property can be handled separately. In this question I assume that the properties of the socks are only accessible via a function that tells whether two socks are identical or different.

There is a paper named Sock sorting, which initially seems related, but actually it deals with another problem, where two socks might seem identical although they are different (this probably makes the problem more difficult).

So, my question is: assuming we only have a binary "identical/different" relation on the socks, can we match the socks faster than $O(n^2)$?

# Answer
A comparison with a result "different" doesn't add information regarding any other sock in the pile (If sock B didn't match A, and Sock C didn't match A, the chance of B and C to be a match is still the same as with any other sock). therefor no sorting or organization can be made, rather then knowing for each sock which socks don't match it based on this comparison. this leads back to the naive algorithm, which is $O(n^2)$.

Pretty disappointing...
> 4 votes

---
Tags: algorithms, time-complexity, sorting
---


title: Tree flattening with layout guarantees

text:
# Question
Title: Tree flattening with layout guarantees
I want to flatten a binary tree into a linear array, and I wonder if there are specific algorithms to improve locality in the linearized representation (for instance, ensuring that all data from the left child of the root node appears before the data from the right child is an easy optimization.) What is the recommended approach to maintain high locality?

# Answer
> 2 votes
one solution might be Van Emde Boas layout (vEB). It is used in a hierarchical memory to optimize the number of cache misses (since it is a cache-oblivious method).

Here is how we lay a complete binary tree that has $N$ nodes in an array: split the tree in the middle (i.e. at height $h/2$ where $h= \log N + 1$). This breaks the tree into a top subtree $T\_0$ of height $\lceil h/2 \rceil$ and several bottom subtrees $T\_1,...,T\_k$ of height $\lfloor h/2 \rfloor$, each dangling from a leaf of $T\_0$. Now store $T\_0$ in the first part of array and the bottom subtrees next to it, in the order from left to right. You need to store each $T\_i$ recursively, i.e. beaking into smaller subtrees until the subtrees contains only one node.

http://erikdemaine.org/papers/BRICS2002/paper.pdf

---
Tags: binary-trees, performance
---


title: DFA / NFA Regular Languages

text:
# Question
Title: DFA / NFA Regular Languages
Consider the non-deterministic finite automaton A: (in below figure)

**1\> convert this NFA to DFA**

**2\> Find if there are equivalent states of your DFA**

**3\> Minimize the DFA of \<2\> if possible**

This is what i have got so far

**4\> further question: Prove that the DFA in \<3\> recogniese the intended language L.**

I got stuck on this question, since the language says that **"every occurrence of a is preceded by and followed by an occurrence of b"** this means:

L = {x bab)^n y | x,y belongs to {b,empty}^n where n is natural number}

In this case: the language can be: **bbb.....bbbb bab ... bab bbb....bbbb**

But for my \<3\> DFA, the occurrence of a can appear without preceded by an occurrence of b.

I hope if there is anyone can point out my mistake.

many thanks

# Answer
Here is the transition table for your NFA:

```
q    s    q'
S0   b    { S1 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }

```

There are a few problems that prevent this from being a DFA:

1. Two valid transitions from state $S\_1$ on $b$;
2. No valid transition from $S\_0$ on $a$;
3. No valid transition from $S\_2$ on $a$.

Problems (1) and (3) can be solved by introducing a new, "dead", state, $S\_3$; the transition table becomes:

```
q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

```

To solve problem (2), we can simply note that the transition $S\_1 \rightarrow bS\_2$ doesn't buy us anything in terms of strings accepted; the only way to get to an accepting state after doing that is to take the transition $S\_2 \rightarrow bS\_1$, and we could simply have applied the transition $S\_1 \rightarrow bS\_1$ twice to do the same thing. We can simply remove this transition and the resulting NFA accepts the same language. Here's the transition table:

```
q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

```

We have no $\lambda$-transitions and each transition maps to a singleton set of states; this defines the following DFA:

```
q    s    q'
S0   b    S1
S0   a    S3
S1   b    S1
S1   a    S2
S2   b    S1
S2   a    S3
S3   b    S3
S3   a    S3

```

Now, we may argue using the Myhill-Nerode theorem to see whether we have redundant states. Consider the ways to get to a string in the language from state $S\_0$. We can see any string in the language (by definition) and end up in an accepting state. This state constitutes an equivalence class we have not yet observed.

Consider $S\_1$. Our first observation is that any string in the language, if encountered starting at this state, will also lead to an accepting state, hence another string in the language. However, we can also see the string $ab$, among others, so this constitutes a new equivalence class, and the state is required.

Consider $S\_2$. Any string in the language, except $\lambda$, leads to an accepting state of the DFA. This is a new equivalence class and the state is not redundant.

Consider $S\_3$. No strings lead from here to an accepting state, so this is yet another equivalence class under the indistinguishability relation, and the state must be kept.

Therefore, the DFA whose transition table is given above is minimal for the language it accepts. Furthermore, it accepts the language of the NFA originally proposed.

To prove the DFA accepts the target language, there are a variety of approaches. The easiest one is actually by stating three facts about the syntax of your DFA, which prevents the excluded condition from occurring in any accepted strings:

1. The transition from $S\_0$ on $a$ leads to a dead state (no string begins with $a$);
2. There is no transition to an accepting state on $a$ (no string ends with $a$);
3. Applying $q \rightarrow aq'$ and $q' \rightarrow aq''$ consecutively always leads to the dead state, where these transitions are any of those in the DFA (no string contains $aa$).

I suppose this is a proof by cases, if knowing what to call the proof is important :D
> 1 votes

---
Tags: regular-languages
---


# Question
Title: Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?
In the chapter, *Approximation Algorithms* of *Introduction to Algorithm, 3rd Edition*, for the approximation problem **Travelling Salesman Problem**, the author proposes a approximation method that first constructs a minimum spanning tree.

In order to prove this algorithm is a 2-approximation algorithm, the author claims that:

The weight of the minimum spanning tree $T$ is less than the cost of the optimal tour.

I am wondering if the minimum spanning tree(which is **acyclic**) of $G$ ensures that its weight is **necessarily** smaller than any tour(which is **cyclic**) of the same graph $G$

PS:

The original claim is:

# Answer
If you take any tour and remove any edge, then you get a spanning tree. Hence the weight of a minimum spanning tree is at most the weight of every tour.

I should add that one of the tricks behind this algorithm is that while we can't find a minimum tour efficiently, we can find a minimum spanning tree. Minimum spanning tree is an efficiently computable relaxation of minimum Hamiltonian path.
> 2 votes

---
Tags: algorithms, graphs, traveling-salesman, approximation-algorithms
---


# Question
Title: How to implement GREEDY-SET-COVER in a way that it runs in linear time
This is an exercise in the book Introduction to Algorithm, 3rd Edition.

The original question is:

Show how to implement GREEDY-SET-COVER in such a way that it runs in time $O(\sum\_{S\in\mathcal{F}}|S|)$.

The GREEDY-SET-COVER in the text book is as follows:

Definition for $(X,\mathcal{F})$ is given as:

# Answer
> 7 votes
Here is some Python code that should implement Greedy Set Cover in linear time:

(Warning, it empties the input sets during the processing!)

```
from collections import defaultdict

F = [set([1,2,3]),
     set([3,4,5,6]),
     set([2])]

# First prepare a list of all sets where each element appears
D = defaultdict(list)
for y,S in enumerate(F):
    for a in S:
        D[a].append(y)

L=defaultdict(set)
# Now place sets into an array that tells us which sets have each size
for x,S in enumerate(F):
    L[len(S)].add(x)

E=[] # Keep track of selected sets
# Now loop over each set size
for sz in range(max(len(S) for S in F),0,-1):
    if sz in L:
        P = L[sz] # set of all sets with size = sz
        while len(P):
            x = P.pop()
            E.append(x)
            for a in F[x]:
                for y in D[a]:
                    if y!=x:
                        S2 = F[y]
                        L[len(S2)].remove(y)
                        S2.remove(a)
                        L[len(S2)].add(y)

print E

```

It uses a dictionary D to store a list of all sets with a particular element.

It uses an array E to store which sets currently have each size. In other words, E\[sz\] will contain information about all the sets that currently have exactly sz elements.

The key to showing that this is linear is to observe that the innermost loop removes an element from a set, so cannot be executed more times than the total number of elements in all sets.

---
Tags: algorithms, algorithm-analysis, time-complexity, greedy-algorithms
---


# Question
Title: Java, strong typing, covariance and contra-variance
While studying for a test in my OOP course, I came upon this question which had an answer I didn't really understand. The question is as follows (translated):

The programming language "Sava" is similar to Java in every way except in the following:

1. It's structurally typed
2. When overriding a method the argument can be contravariant and the return type can be covariant.

Given the following class and interface, is the following assignment legal?

```
  interface I{
    boolean equals(I i){…}
  }

  class C{
    boolean equals(C c){…}
  }

I i = new C();

```

The answer that was given to this question was: The assignment isn't legal. The equals method in C changes the paramater in a covariant way and so it doesn't match the equals method in I.

At first I thought the professor forgot to add "Implements I" but the answer also stated the following: Answers that refereed to the fact that C doesn't implement I weren't accepted because given that it's a Structurally Typed language it doesn't matter if it were a subtype.

I'm not sure I understand how we can refer to these methods as covariant / contravariant if there is no relation of subtyping between C and I.

Can anyone clear this up for me?

# Answer
> 2 votes
"Structurally typed" means that you don't need to write `implements I`: if your type has all the methods `I` has, with compatible signatures, it's automatically a subtype of `I`. However, in this case, `C.equals(C)` does *not* implement `I.equals(I)` (due to variance) and so `C` isn't a subtype of `I`.

EDIT:

> I'll explain: For C to be structurally equivalent to I we need to know the type hierarchy for the arguments of equals.

Yes, here you have recursive structural types, which complicate the issue quite a bit.

> The equals method in C changes the paramater in a covariant way and so it doesn't match the equals method in I.

This is strictly speaking incorrect, this isn't covariant (again, since `C` isn't a subtype of `I`). It should instead say e.g. "if we assume `C` is a subtype of `I`, then the equals method in `C` changes the parameter in a covariant way and we get a contradiction". You could claim `C` and `I` should be treated as *equivalent* (i.e. both subtypes of each other), and then there is no contradiction.

Another problem is that definition of `C` depends on `C` itself, so you have recursive structural types, which complicate the language quite a bit.

---
Tags: type-theory, java
---


title: Points-in-a-plane from HackerRank

text:
# Question
Title: Points-in-a-plane from HackerRank
I've been struggling with this problem for days now, making no progress:

> There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your goal is to remove all the points in the least number of turns. Given the coordinates of the points, calculate two things:
>
> * The minimum number of turns (T) needed to remove all the points.
> * The number of ways to to remove them in T turns. Two ways are considered different if any point is removed in a different turn.

-- https://www.hackerrank.com/challenges/points-in-a-plane

I've tried a greedy exhaustive solution, where I draw a line between each pair of points, then start to eliminate the lines in descending order based on the number of points they cross. Unfortunately, there is at least one case where this approach produces suboptimal results:

For ease of discussion, I will call lines "longer" or "shorter", based on how many points they include. The greedy algorithm is simply to eliminate lines in order of descending length.

Suppose we have a set of N longer lines, and another set of M shorter lines. Our greedy algorithm will eliminate the long lines first. But what if every single point of the long lines is also included in a short line? In that case,our initial elimination of the N longer line was a waste, since we would have gotten those lines "for free" had we just eliminated the shorter lines. Specifically, our greedy approach will require N + M eliminations, where we could have cleared all points in just M steps.

The simplest example input demonstrating this is:

```
(0, 1), (1, 2), (2, 4), (3, 3)
(0, 0), (1, 0), (2, 0), (3, 0)
(0,-1), (1,-2), (2,-4), (3,-3)

```

As you can see, we have a line of length 4 running along the X axis, and 4 shorter vertial lines of length 3 perpendicular to it. Our greedy algorithm will first eliminate the longest line, after which there will be 8 sets of points remaining, with no more than 2 of them collinear. Eliminating those will thus take 4 steps, for a total 5, where we could have eliminated all points in just 4 steps, had we simply eliminated the 4 vertical lines first.

Could someone provide at least a hint at the general body of knowledge required to approach this? I solved many other HackerRank questions, but can't make any headway with this one.

# Answer
this is the problem of covering points with lines or linear facility location which is NP-Hard. This is why you couldn't find a greedy solution. There are approximation and exact algorithms for this problem. If you want an exact algorithm that is efficient on large inputs I suggest you a simple version of parametrized solution for this problem.
> 4 votes

# Answer
* find all the \[sets of\] colinear points. create an array of them, or basically an array of arrays. each is a set. there seems to be a polynomial bound of lines in terms of points. (exercise: prove it)
* solve with set cover. set cover was one of the original NP-complete problems discovered by Karp 1972. NP completeness is the "general body of knowledge required to approach this". there are indeed "greedy" algorithms for this problem but note that greedy algorithms are generally not "exhaustive" because they get stuck in local minima.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to purge a linked list in $\mathcal{O}(n\log n)$ time?
I was wondering how to remove duplicate values from a linked list in $\mathcal{O}(n\lg n)$ time. I have an idea that by using merge sort when we want to compare elements for choosing the small one, if they are equal advance on pointer and just consider one element. Any alternatives?

# Answer
> 3 votes
1. Sort the linked list in $O(n \log n)$ time.
2. Go through each element of the list in their order and remove the element, if it is the same as the previous one in $O(n)$ time.

The total complexity is $O(n \log n)$, which is what you are searching for.

# Answer
> 4 votes
You can do it in $O(n)$ as follows.

1) Build an hash table by traversing the linked list and adding its elements to the hash table. In each iteration, search the hash table for the current element being considered in the iteration. If the element is not found, add to the hash table the element value as the key, and 1 as the corresponding value. If you instead find the element (which has been inserted in a previous iteration), you simply add 1 to the corresponding value and update the hash table entry (correctly updating the element multiplicity). At the end, your hash table will contain at most $n$ entries (this corresponds to the case that the element in the linked list are distinct), or less than $n$ elements, with at least one of the entries showing a multiplicity greater than one. This takes $O(n)$ time since in each of the $n$ iterations the work done on the hash table is $O(1)$.

2) Now, traverse the hash table and build a new linked list by adding a node for each element found. this takes at most $O(n)$ since the hash table contains at most $n$ elements, the work done on each element of the hash table is $O(1)$ and adding a node to the new list takes $O(1)$.

Therefore, the total complexity is at most $O(n)$.

---
Tags: sorting, linked-lists
---


title: Functional Programming and Parallelism

text:
# Question
Title: Functional Programming and Parallelism
I have an option to learn a new language for parallel computing. As a parallel programmer what are the reasons one might want to invest time to learn functional programming for parallel computing?

# Answer
> 4 votes
An important argument for learning one is that operations in a purely functional language does not have **side effects**.

In this case that means one operation cannot change the state of another parallel operation. That makes it much easier to reason about the behaviour of your program, since you don't need to account for all the possible combinations of states, but rather the input and output of each function.

Some functional languages have both purely functional operations and destructive operations (like Lisp and Scheme) and some have only the former (like Haskell). Which one you choose is dependent on what you are trying to solve.

---
Tags: parallel-computing, functional-programming
---


# Question
Title: Converting a 2-SAT formula into an implication graph
Both wikipedia and my lecturer explained how the 2 satisfiability problem work. However, I am finding it really hard understanding how this formula:

```
xvy≡ ¬x-->y ≡ ¬y -->x

```

Then breaks down the following conjectures :

```
(¬x v y) & (¬y v z) & (¬z v w) & (¬w v ¬x) &
(x v ¬y) & (y v ¬z) & (z v ¬w) & (w v x)

```

is converted to an implcation graph.

Heres my attempt:

```
 (¬x v y) = (¬y-->x)

          = (¬x-->y)

```

but this cannot be right, as they have diffrent truth tables:

```
(¬y-->x)

```

1 0 **0** 0

1 0 **1** 1

0 1 **1** 0

0 1 **1** 1

```
(¬ x-->y)

```

1 0 **0** 0

0 1 **1** 1

1 0 **0** 0

0 1 **1** 1

I understand once you have the conjectures converted to implication, how to construct the implication graph and find out if its not satisfiable (bad loops).

Could someone please explain clearly how to break down the conjectures to implications?

# Answer
> 6 votes
> ```
>  (¬x v y) = (¬y-->x)
>
> ```

$$\begin{align} \text{rule: } &A \vee B &=& (\neg A \implies B)\\ & \neg x \vee y &=& (\neg\neg x \implies y)\\ & &=& (x \implies y) &(1)\\ \end{align} $$

> ```
>           = (¬x-->y)
>
> ```

So now this becomes:

$$\begin{align} \text{rule: } &A \implies B &=& (\neg B \implies \neg A)\\ &(x \implies y) &=& (\neg y \implies \neg x) & (2) \end{align} $$

And we get:

$$\begin{align} (x \implies y) & (1)\\ (\neg y \implies \neg x) & (2) \end{align} $$

And the truth table:

$$ \left.\begin{array}{rrrr} x & y & (\neg x \vee y) & (x \implies y) & (\neg y \implies \neg x) \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array}\right. $$

As you can see they are equivalent.

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Reasons for decreasing the number of threads in a parallel implementation
What are the reasons for decreasing the number of threads in a parallel implementation ?

Assume that we have two implementations, the first one with 4 threads, and a second one with 8 threads, and both have exactly the same run time. What are the various reasons to prefer the first one?

I stress on the fact that the two implementations have the same run times.

The obvious reasons are the following:

* If we have 8 processors, we can execute at the same time this implementation on two different sets of inputs thus performing twice the work,
* Less resources consumption by the OS which handles less number of threads.

I'm looking for other reasons...

# Answer
Some other benefits from a security point of view for running the 4 threads implementation would be :

* **Obfuscation** of the actual processors being used by the algorithm, in case an attacker is looking to interfere with the execution.
* If you have 8 processors you can run simultaneously the same algorithm twice using the same input to check the **integrity** of your results.
> 3 votes

# Answer
Obviously, an algorithm that takes 4 threads one minute each is better than an algorithm that takes 8 threads one minute each. The solution that only needs 4 threads/processors uses half as much energy as the one that needs 8 threads/processors. Also, if you have 8 processors, the former leaves 4 processors idle and free to work on other tasks. Finally, if you have fewer than 8 processors, the latter will probably see contention and will in practice run longer.

Is this a real problem? The answer seems so clearcut; there's no reason to prefer the solution that does twice as much work in total.
> 2 votes

# Answer
* If you have less processors than the number of threads, this will cause contention of the thread scheduling over the CPUs (the OS will have to context switch between threads, because there are more threads than CPUs).
* If the threads access a single resource, more threads will cause more contention (threads will have to wait for eachother); thus sometimes increasing the number of threads will not benefit a program; it can even harm the performance, as now there is a lot more OS/CPU handling/management of the critical sections.
> 1 votes

---
Tags: parallel-computing, threads
---


# Question
Title: What happens when an alphabet is not listed in a Turing Machine?
I was given a quick lesson on Turing Machines which I found interesting. However, I came up with a problem which made me think a bit on a problem and since it's not an actual class, the answer was not given. First, let me give you some background info on a Turing Machine:

```
A Turing machine is a quadruple (K, sigma, small delta, s), where
  K is a finite set of states, not containing the halt stage h;
  sigma is an alphabet, containing the blank symbol #, but not containing symbols L and R;
  s is in K is the initial state;
  small delta is the rate of change.

```

With that info in mind, I have the following problem:

```
Consider the Turing machine M = (K, sigma, small delta, s), where
  K = {q0,q1} //only has two states
  sigma = {a,#} //only has a and the blank symbol
  s = q0 //will start at 10

and small delta is given by the following table.
  q      small sigma      small delta(q,small sigma)
  q0      a                 (q1,#)
  q0      #                 (h,#)
  q1      a                 (q0,a)
  q1      #                 (q0,R) //move one cell of the tape to the right

```

With this info and the following example, we have:

```
a|a|#

```

Let's check the first cell, it's a and we are in the initial state. If it's a, change it to #.

```
#|a|#

```

We're still on the same cell, but we changed states, q1. The alphabet is #, so let's go back to the initial state and go one cell to the Right.

The next cell has an a as well, so we change it to #. Go to state q1 and check if the alphabet is blank. It is, so we go one cell to the right.

```
#|#|#<we're in this cell now.

```

Now we go to the initial state and check if the alphabet is a, it isn't so let's check if it's blank. It is, so we halt the whole thing.

We have

```
#|#|#

```

Pretty straightforward, right? Well, I have thought of one thing. What if the tape had something that was not taken into consideration?

Something like

```
a|b|a|#

```

Would the Turing machine crash or would it ignore it?

Thank you for your time.

# Answer
The behavior of the Turing machine is not defined in this case. So, the mathematical formalism does not predict or require anything about how the machine will behave in such a circumstance.

Since a Turing machine is only a mathematical construct anyway, it's perfectly reasonable to impose such a limitation and only think about what happens when you run it on a tape that follows all the rules.

Put another way: If it's possible for the symbol `b` to occur in the tape, then it's your job to make sure that `b` is included in the alphabet.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Double, down facing arrow in operational semantics
What is the meaning of the double, down facing arrow $\Downarrow$ in the context of operational semantics? Here's the example formula that uses it:

$$\frac{s\_0 \vdash M\_1 \Downarrow P\_1, s\_1 \\; ... \\; s\_{n-1} \vdash M\_n \Downarrow P\_n, s\_n}{s\_0 \vdash M \Downarrow P, s\_n}$$

It would be also beyond priceless if you could explain in words what do other pictograms of this formula mean. I feel that $\vdash$ here doesn't mean what it usually means in logic (is provable from). However the general form of this formula is the derivation rule (I can understand it from the context). It is a rather general derivation rule though (it is followed by few other more specific examples which use all the same pictograms).

The source of the formula: On Exceptions versus Continuation in the Presence of State by Hayo Thielecke. It cites several other sources, but I couldn't find the explanation of the symbols used.

# Answer
> 6 votes
The language of inference rules are much more general than what is usually given in Logic. Indeed you can look at systems with rules of the shape

$$ \frac{\Theta\_1\ldots \Theta\_n}{\Theta}$$

Where the $\Theta\_i, \Theta$ are some kind of statement and ask: what are all the possible $\Theta$ I can get by repeated application of these rules?

In the above case, $s \vdash M \Downarrow P, s'$ expresses the statement:

> With starting state $s$, program $M$ evaluates to $P$ and the resulting state is $s'$.

This is a very general framework for expressing the operational semantics of a program, and it means that if you can build a finite derivation tree with $s \vdash M\Downarrow P, s'$ at the base, then you have shown that the program $M$ is well-defined and evaluates to $P$.

Let's give an example. Say $s$ is the state in which variable $b$ is sent to `true` and $n$ is sent to $2$, which I will write $\\{b\mapsto \mathrm{true}, n\mapsto 2 \\}$. Then the following should be derivable:

$$\\{b\mapsto \mathrm{true}, n\mapsto 2 \\}\vdash \mathrm{if}\ b\ \mathrm{then}\ n+1\ \mathrm{else}\ 0 \Downarrow 3, \\{b\mapsto \mathrm{true}, n\mapsto 2 \\}$$

Note that in your question, the rule:

$$\frac{s\_0 \vdash M\_1 \Downarrow P\_1, s\_1 \\; ... \\; s\_{n-1} \vdash M\_n \Downarrow P\_n, s\_n}{s\_0 \vdash M \Downarrow P, s\_n}$$

Means:

> If, starting from state $s\_0$, $M\_1$ reduces to $P\_1$ and new state $s\_1$, **and starting with state $s\_1$** $M\_2$ reduces to $P\_2$ and new state $s\_2$ etc. then starting from state $s\_0$, $M$ reduces to $P$ with new state $s\_n$.

In particular, the order in which you do the reduction is important: the state may change after the evaluation of $M\_1$, which in turn will influence the evaluation of $M\_2$, etc. This is why in a language with state (side-effects), the order of evaluation of arguments passed to a function is important: we may get a different result depending on which argument we evaluate first.

In Haskell, laziness makes it impossible to know which arguments will be evaluated first (or at all!), so having side effects is pretty much out of the question.

I suggest reading the classic Types and Programming Languages, by Benjamin Pierce, which treats all of this in much detail.

# Answer
> 3 votes
There are two systems of operational semantics: small-step and big step. The symbol $\Downarrow$ is used in the latter to denote "this term evaluates to that final value". E.g., $t \Downarrow v$. There is a short discussion of the system in Pierce's *Types and Programming Languages* pages 42-43.

The $\vdash$ is used to imply that if the types on the left hand side are true, then the ones on the right hand side can be derived. Further explanation is given in Pierce's book.

---
Tags: terminology, semantics, operational-semantics
---


# Question
Title: Is $\log{n}$ bounded from above by $n^{o(1)}$?
Let $O(n)$ be "Big-O" of $n$ and $o(n)$ be "Small-O" of $n$.

It is a well-known fact that $O(n \log{n}) \subset O(n^{1 + \epsilon})$ for any $\epsilon \> 0$. Can we omit the $\epsilon$, and just type $O(n \log{n}) \subset O(n^{1 + o(1)})$?

# Answer
Consider the function $f(n) = n^{1 + \frac{1}{n}}$ which I guess you'd say is in "$O(n^{1 + o(1)})$". I'm not sure you can call it polynomial, though.

Now, compute

$\qquad \displaystyle \lim\_{n \to \infty} \frac{n^{1 + \frac{1}{n}}}{n \log n} = 0$,

so you have in fact that $f \in o(n \log n)$. Therefore, functions in this funky class of yours are not even (all) asymptotic upper bounds for $n \log n$.

The difference is that $\varepsilon$ ensures a non-vanishing distance from $n^1$ whereas $o(1)$ means that functions of the form $n^{1 + o(1)}$ in fact *converge* towards $n \in o(n \log n)$.
> 6 votes

# Answer
Common usage would have $n\log n = n^{1 + o(1)}$. This is a shortcut for $n\log n = n^{1 + f(n)}$ for some function $f(n)$ satisfying $f(n) = o(1)$. In our case, this function is $f(n) = \log \log n / \log n$, which indeed satisfies $f(n) = o(1)$.
> 6 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: need of error control in transport layer
I want to know why error control is used in transport layer although it is used in data link layer?While data link layer has all data came from upper layers in its frames so its error control should be sufficient.

# Answer
There are many types of error controls. The link layer error control that you are referring to is probably to do with ensuring that no bits were flipped in transit i.e. safe guarding against data corruption.

The error control in the transport layer usually refers to the guaranteed delivery mechanism with TCP, which attempts to safe guard against frames/packets getting lost entirely.
> 1 votes

---
Tags: computer-networks
---


title: Numbering of unlabelled trees

text:
# Question
Title: Numbering of unlabelled trees
For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?

# Answer
According to Wikipedia, a closed-form formula for the number of unlabelled trees is not known, so a numbering in the form of a bijection between the set of unlabelled trees on $n$ vertices and $\\{1,\ldots,T\_n\\}$ (for an appropriate $T\_n$) is probably hopeless. Tree isomorphism is in P, so if you want an "effectively unique" identifier for trees, you can get it by using the Prüfer numbering and applying the algorithm to test equality. It is also possible that you can canonicalize trees (using the same ideas as in the algorithm), thereby creating a coding scheme in which two isomorphic trees get the same (Prüfer) number.
> 3 votes

---
Tags: trees
---


title: Snowball Question FFT

text:
# Question
Title: Snowball Question FFT
http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf

I'm confused as to the solution for the snowball question. To start with, I have two specific questions:

(1) Each pair $a\_i,b\_j$ will account for one term (and why ONE term)? What is meant by term here? The coefficient, $c\_k$ of the polynomial C? Or maybe the $x$ value at the $kth$ spot?

(2) Why is $c\_k$ the number of such pairs?

# Answer
Here is the idea of the proof. Let $a\_i,b\_i$ be the distance thrown by the $i$th male/female. Using FFT, we calculate $$ \left(\sum\_i x^{a\_i}\right) \left(\sum\_j x^{b\_j}\right) = \sum\_{i,j} x^{a\_i+b\_j}. $$ Each pair $i,j$ satisfying $a\_i + b\_j = k$ contributes one term $x^k$ to the polynomial on the right. Hence the coefficient of $x^k$ is the number of pairs $i,j$ such that $a\_i + b\_j = k$.

If things still aren't clear, I suggest you try a few examples.
> 1 votes

---
Tags: algorithms, fourier-transform, polynomials
---


title: Selection of K elements of given ranks

text:
# Question
Title: Selection of K elements of given ranks
Given a procedure/function

$Select(S,r)$ - which selects element of rank r from set S which uses at most $|S|. constant$ comparisons

We design another function $Multiselect(S,R)$ with $R =\\{r\_1\<r\_2\<...\<r\_k\\}$
returns $X =\\{x\_1\<x\_2\<...\<x\_k\\}$ such that rank of $x\_i$ is $r\_i$

What is the minimum no of comparisons for this function?

From Wikipedia I found the upper bound for it -

But while utilising this for deriving the answer I got it totally messed up!
I tried using algorithm to utilise Select(S,r) repeatedly each time
each time decreasing the search space by logn ... but I guess the answer could be found
in a more concise mathematical way.

By the way, answer given was - $constant.|S|(1+logR)$

# Answer
Hint: Find first the element of rank $r\_{(k+1)/2}$, and split the list accordingly into two parts $S\_1,S\_2$ satisfying $|S\_1| + |S\_2| = |S|$. Now repeat.
> 1 votes

---
Tags: complexity-theory, algorithm-analysis
---


title: Any path detecting between A to B

text:
# Question
Title: Any path detecting between A to B
In my world there are nodes and lines, I want to see if there is any path between node A, and node B, that do not cross any line(including the lines of the path itself) and do not go thru the same node twice. What would be the efficiency of such algorithm and where can I find more information about it.

So far I been reading about A\* algorithm, but I do not need the shortest path, just to see if there is any path like this exist at all.

# Answer
***Depth-first search*** or ***Breadth-first search***. Note that Dijkstra's algorithm, essentially reduces to breadth-first-search with equal-cost-paths.

You can also do a sort of meet-in-the-middle (known as a ***bidirectional search***), starting a search from both ends.

Any algorithm for detecting ***connected-components*** will work here as well (again, these essentially using one of the search algorithms and adding connected nodes to some collection). However, you can perhaps use the some sort of ***disjoint-set-data-structure*** to keep track of different components as you add "lines" into the graph, and thus quickly test if the component of $A$ is the same as $B$. See also: ***connected-component labeling***, and ***partition refinement***.

If your nodes have a special structure, you might be able to take advantage of it. For example, if you are thinking of nodes in euclidean space, you can use a ***spatial-index***, such as a ***quad-tree***, to speed the traversal/search by traversing whole globs of nodes in one shot when it is far from a line/obstacle. Another example would be to use A\*, even if you don't care about shortest-path, it might be better than simple breadth-first/depth-first, because of the structure and heuristic you can provide (see best-first search and beam-search).

**EDIT:**

I thought of another formulation of the problem (which likely would use one or a combination of the above approaches): Is there an online-algorithm to keep track of components in a changing undirected graph:

>
> 2 votes

---
Tags: search-algorithms
---


# Question
Title: Compile a programming language with itself
I'm a computer science student. I want to create my own programming language (A basic language with few instructions).

I know how to do a syntactic analyser, I already did it in Perl. In an article, I read something about the compiler, a compiler is done in itself.

For example the C compiler is written in C. How it's possible? I can make my own language but I don't know how I could execute it? Any idea?

It's really a good question and I can write a blog the project.

# Answer
The trick is *bootstrapping*. You first write a compiler for your language (or a subset thereof) in some other language. Then you write a compiler for your language (or a large subset of the one you can already handle) in your language. You use the former compiler to compile the new compiler, and then the new compiler can compile itself.
> 15 votes

# Answer
A compiler which can compile its own sources is called a self-hosting compiler. Early compilers were written in another language. For example, the first C compiler was probably written in assembler. The whole trick in using a former lower level compiler is called bootstrapping.
> 3 votes

---
Tags: programming-languages, compilers
---


title: Proving $f = \Omega (h)$

text:
# Question
Title: Proving $f = \Omega (h)$
I need to prove that $n^4+2n = \Omega (n^2)$

Which means I need to point two constants $c\_1,c\_2$ that from $n\_0$: $$ c\_1 \leq \frac{\log(n^4+2n)}{\log(n^2)} \leq c\_2$$

Now I know that: $\lim\_{n \to \infty } \frac{\log(n^4+2n)}{\log(n^2)} = 2$ so I can choose $c\_1 = 0.5$ and $c\_2 = 3$ but how do I do I calculate the $n\_0$ that this sentence become true to?

# Answer
> 2 votes
You are working harder than you have to. There are lots of ways to prove this but in general the idea is that you should just find some constants that work, not worry about finding precise small constants.

In this case we don't even need constants! Assuming $n \geq 1$, we have $$n^4 + 2n \geq n^4$$ always. And $$n^4 \geq n^2$$ always.

So $n^4 + 2n \geq n^2$, which means $n^4 = \Omega(n^2)$.

...

An easier definition of $\Omega$ is that you need to find a positive constant $C$ so that $$C(n^4 + 2n) \geq n^2$$. As mentioned above, $C = 1$ works!

...

Finally, for your example, as in the comment on cstheory, if you want to do it your way, you can always just pick a really high $n\_0$ and check that it does indeed work. In general, you can try to solve the equation $C(n^4 + 2n) = n^2$ for $n$, once you have picked a constant $C$ using your limit approach.

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


# Question
Title: How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n
How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ?

for example : for n=10 1 2 3 4 10 20 30 40 100 200

the sub-sequence of length will with minimized sum of difference will be 1 2 3 4 as |1-2| + |1-3| + |1-4| + |2-3| + |2-4| + |3-4| = 10 i.e minimum in any sequence.

# Answer
Where are the constraints? Well, since I don't know what the constraints are, I will help you with an almost naive solution. For each segment of length `k` (so there are `n-k+1` segments) you have to order the elements, because if you have an ordered array then you can calculate that cost function of the segment as follow. For example:

```
array: 1 2 3 4

```

The cost function as you said is:

```
|1-2| + |1-3| + |1-4| + |2-3| + |2-4| + |3-4|

```

and it is equal to:

```
2-1 + 3-1 + 4-1 + 3-2 + 4-2 + 4-3 = 10

```

and it is equal to:

```
4*3 + 3*2 + 2*1 + 1*0 - 1*3 - 2*2 - 3*1 - 4*0 = 10

```

So as you can see for a general ordered array:

```
array: a0, a1, a2, ..., an-1 ; a0 <= a1 <= a2 <= a3.. <= an-2 <= an-1

```

The cost function can be calculated as:

```
an-1*(n-1) - an-1*(0) + an-2*(n-2) - an-2*(1)... + ak*k - ak*(n-1-k) + ... + a0*(0) - a0*(n-1)

```

So the time complexity for the cost function will be `O(k)`, and the total cost will be `O((n - k + 1) * (k * logk + k)) = O(n*k*logk)`.
> 0 votes

---
Tags: algorithms, dynamic-programming, linear-programming, greedy-algorithms, constraint-programming
---


# Question
Title: exact matching between two strings - linear edit distance?
This is the problem, given a string with characters from: `a-z`, `.`, `*`, and another string with characters from `a-z`. where `*` can delete the character before it, otherwise `*` is skipped and `.` can match any single character. the question is whether the first string can match the second one.

**Note:** That is the statement of the problem as I found, but in this case the character `*` performs the same function that `?` in a regular expression.

Example:

```
isMatch("a*", "") = true; //"a*" could be "a" or an empty string ""
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;

```

I've already solved this problem using a slightly modified edit distance, which I only know a 2D dynamic programming approach. I wonder whether exists a linear solution for this problem, maybe it is solvable without a dp approach?

# Answer
As far as I understand you cannot solve the problem in linear time. If in the first string every character `a-z` is followed by `*`, the problem coincides with substring matching. So, isMatch("a?a?b?b?b?a?b?a?b?a?","abba") asks whether `abba` is a subsequence of `aabbbababa`.
> 2 votes

---
Tags: algorithms, dynamic-programming, regular-expressions, strings
---


# Question
Title: Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?
Let $PAL = \\{ww^R\ | w\in\\{0,1\\}^\*\\}$.

Then let $A = \\{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\\}$

Is A semi-decidable (Turing recognizable or recursively enumerable)?

My try!

I said it is so here is my proof, tell me if I am way off base or tell me if A ought not to semi-decidable in the first place.

$\underline{Proof}$

A is semi-decidable by The Certificate Theorem, which states that:

If $A\subseteq\Sigma^\*$ then $A\in SD$(semi-decidable) iff there is some decidable relation, $R\subseteq \Sigma^\* \times \Sigma^\*$, such that $\forall x\in\Sigma^\*$, $x\in{A}$ iff $\exists y$ such that $R(x,y)$ holds.

We know that if $x\in{A}$ that means that $x=\langle M\rangle$, so we can choose $y = \langle M,w\rangle$ where $w\in{PAL}$. What we know is that when $M$ takes $w$ as an input it will accept (since we choose $w$ as an input), if that is the case then $w\in{L(M)}\subseteq{PAL}$. That means that $A\in{SD}$. QED

Any help would be greatly appreciated, have a great day!

# Answer
> 1 votes
What you have shown is that the language of Turing machines accepting *at least one* even palindrome is semi-decidable. However, your question is interested in the language of Turing machines accepting *only* even palindromes, which is rather different. The complement of this language is the language of Turing machines accepting *at least one* word which *isn't* an even palindrome, and so *the complement* is semi-decidable according to your argument. This still leaves open the question of whether the *original* language is semi-decidable (and so decidable).

# Answer
> 1 votes
My first hint is that your proof of $A \in SD$ is wrong. Assume that $M$ accepts only even palindromes, how are we supposed to certify that?

However, if you look at $\bar{A}$, which consists of $\langle M \rangle$ such that $L(M) \not \subseteq PAL$, so $M$ must accept some string which not even palindrome. Hint: Can we apply the Certificate Theorem for this case? If so then $\bar{A} \in SD$.

It remains to show if $\bar{A}$ is decidable. If you can show that $\bar{A}$ is undecidable, then we can easily conclude $A\not \in SD$. (How?)

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


title: Suffix trees - "smaller half trick"

text:
# Question
Title: Suffix trees - "smaller half trick"
I have been reading a paper Finding Maximal Pairs with Bounded Gap:

An in there, there is a sentence (page 6 second paragraph):

> The “smaller-half trick” is used in several methods for finding tandem repeats, e.g. \[2, 5, 26\]. It says that the sum over all nodes *v* in an arbitrary binary tree of size *n* of terms that are $O(n\_{1})$, where $n\_{1}\leq n\_{2}$ are the numbers of leaves in the subtrees rooted at the two children of *v*, is $O(n\log n)$

Although it sounds very straightforward, I just cannot see why this is true. Could someone with some experience regarding this trick please explain why this is true? I read several other papers but just don't see it.

# Answer
> 2 votes
We prove by induction on $n$ that your sum (with $O(n\_1)$ replaced with $n\_1$, only taken over non-leaves) is at most $n\log\_2 n$. We use the convention $0\log\_2 0 = 0$. The base case $n$ = 0 trivially holds, since the sum is empty. Now suppose we have a node with subtrees of sizes $n\_1 \leq n\_2$; this implies that $n = n\_1 + n\_2 + 1$. The sum is at most $$ S = n\_1\log n\_1 + n\_2\log n\_2 + n\_1. $$ Let's concentrate on the first two terms: $$ \begin{align\*} n\_1\log n\_1 + n\_2\log n\_2 &= (n\_1 + n\_2) \left\[ \frac{n\_1}{n\_1+n\_2} \log n\_1 + \frac{n\_2}{n\_1+n2} \log n\_2 \right\] \\ &= (n\_1 + n\_2) \left\[ \frac{n\_1}{n\_1+n\_2} \log \frac{n\_1}{n\_1+n\_2} + \frac{n\_2}{n\_1+n\_2} \log \frac{n\_2}{n\_1+n\_2} + \log (n\_1+n\_2) \right\] \\ &= (n\_1+n\_2) \[\log(n\_1+n\_2) - h(\tfrac{n\_1}{n\_1+n\_2})\], \end{align\*} $$ where $h(p)$ is the binary entropy function. Let $p = n\_1/(n\_1+n\_2) \leq 1/2$. Then we can bound $S$ by $$ n \log n + (n\_1+n\_2)(p-h(p)). $$ One checks that $p \leq h(p)$ for $0 \leq p \leq 1/2$, completing the proof. (In fact, $2p \leq h(p)$, so we can get the better bound $\tfrac{1}{2}n\log\_2 n$, which is nearly tight for complete binary trees.)

---
Tags: data-structures, strings, suffix-trees
---


# Question
Title: Deterministic Random access machine and polynomial time
How do we prove $M$ that is a deterministic random access machine that decides a problem $A$ for an input $i$, and $u\_M(i)$ is the set of addresses of those registers that occur at least once with $s$ steps and a configuration of $C\_0,\dots,C\_s$ where each configuration is of the form $C\_i=(k\_i,R\_i)$, were $k\_i$ is the program counter and a mapping $R\_i$ runs in polynomial time if it runs in logarithmic space.

# Answer
> 1 votes
Hint: If the program runs in logarithmic space then there are only polynomially many possible configurations.

---
Tags: complexity-theory, polynomial-time
---


title: Sort edges in euclidean graph

text:
# Question
Title: Sort edges in euclidean graph
Given a euclidean graph $G$ and a node $p$ with edges to all the other nodes, is there a more efficient solution than $O(NLog(N))$ to output all the edges to $p$ in sorted order?

# Answer
If you find a way to do this, then you can build a sorting algorithm that does it faster than the $\Omega(n \log n)$ boundary on comparison sort.

How you would build the sorting algorithm: let the values in an $n$-element array by $x\_1,...,x\_n$. Assume you can find the neighbors of a vertex on the euclidean plane sorted by distance in $\mathcal{o}(n \log n)$ time. Use the vertex $v\_0 = (\text{min}\_i \\{x\_i\\} -1,0)$ as reference vertex, put vertices $v\_1,...,v\_n$ on the x-axis with $v\_i = (x\_i,0)$. Clearly, those points sorted by their euclidean distance from $v\_0$ give you the order for the array as well. This way, you would get below the comparison-sort boundary of $\Omega(n \log n)$. Given that there is no known sorting algorithm like that that doesn't also have some other variables in its complexity, I'd expect that finding such an algorithm would be really hard.
> 3 votes

---
Tags: graphs, computational-geometry
---