# Question
Title: Should O(1) necessarily stand for a non-zero constant?
I had a debate with my friend. He argued that $o(1)\subseteq O(1)$, so if a function converges to 0, then it belongs to both $o(1)$ and $O(1)$. However I imagine that $O(1)$ represents a constant time, in essence, a non-zero constant time. Is there a broad acceptance that a function converging to zero belongs to $o(1)$ and not to $O(1)$?

# Answer
> 9 votes
$O(1)$ does not represent time. It represents a class of functions, which could be used to measure time, space or literally anything else.

$f(x)\in O(1)$ if, and only if, there is a constant $c$ such that $f(x)\<c$ for all large enough $x$. There's no requirement that $f$ must be eventually non-zero. $f(x)\in o(1)$ if, and only if, $\lim\_{x\to\infty} f(x) = 0$ so, in particular, for all large enough $x$, $f(x)\<1$. Therefore, $f(x)\in O(1)$.

# Answer
> -2 votes
I'm going to try to answer a slightly different question than you asked, namely, what the difference is between big-oh and little-oh, and how can you build some good intuition about both of them. If you know that, then the answer to your question is obvious.

I'm also going to ignore absolute values here for the sake of simplicity.

Here's a good way to visualise the difference between big-oh and little-oh. This was never explained to me in this way; I came up with this myself. I hope this helps you, too.

* A function $f(x)$ is $O(g(x))$ if there exists a constant $c\>0$ such that there exists a number $x\_0$ such that $\forall x\>x\_0, f(x) \le cg(x)$.
* A function $f(x)$ is $o(g(x))$ if for all constants $c\>0$ there exists a number $x\_0$ such that $\forall x\>x\_0, f(x) \le cg(x)$.

So the difference between big-oh and little-oh is that big-oh is "there exists a constant $c$", and little-oh is "for all constants $c$".

It should be clear from this alone that if $f(x)$ is $o(g(x))$ then it is also $O(g(x))$. However, there's a wider point here which it's helpful to emphasise.

Informally, $f(x) = O(g(x))$ means that $f(x)$ is eventually within a constant factor of $g(x)$, *and the constant is chosen for you*. If this measures time, then the constant may be a complex interplay between the CPU designers, the laws of physics, how loaded your machine is, and so on. The point is, it's within a constant factor, and the constant factor is not under your control.

However, $f(x) = o(g(x))$ means that $f(x)$ is eventually within a constant factor of $g(x)$, but *you get to pick the constant yourself, and it can be as small as you like*. To rub the point in, we often name the constant $\varepsilon$ instead of $c$, because epsilon carries the connotation of "arbitrarily small".

Please let that point sink in before you read on.

Little-oh notation is far more commonly used in space analysis than time analysis, because in time analysis, we typically care about "wall time" (i.e. the time according to a clock on the wall), which invariably changes when you run the same algorithm on a new computer. However, in space analysis, we care about bits, or gigabytes, or something like that. A bit may be *physically* smaller when a new RAM chip or hard disk gets released, but it's not *logically* smaller. A bit always can only store one bit of information at the most.

So suppose that you are designing a data structure which information theory states must use at least $f(n)$ bits (say, if you're storing $n$ things in it).

* A data structure which uses $f(n) + O(1)$ bits is called *implicit*.
* A data structure which uses $f(n) + O(f(n)) = \left( 1 + O(1) \right) f(n)$ bits is called *compact*.
* A data structure which uses $f(n) + o(f(n)) = \left( 1 + o(1) \right) f(n)$ bits is called *succinct*.

Informally, a compact data structure has constant relative overhead. This might mean 1%, 5%, or 10 times. That last one might not be as useful as 1% overhead, but still. The point is that the relative overhead (compared to a theoretically perfect solution) is a constant.

A succinct data structure, on the other hand, has a relative overhead which is *eventually insignificant*.

It should be clear from the above definitions that a data structure that is implicit is automatically succinct, and a data structure that is succinct is automatically compact.

---
Tags: terminology, asymptotics
---


# Question
Title: Data Compression: Which one is Better "Compress before Encrypt" or "Encrypt before Compression"
Which one is better approach do data compression before encrypting it or Encrypt data before compression ? I think it is biased towards the application requirement. Please share your views.

# Answer
Compressing encrypted data doesn't work. Encrypted data looks pseudorandom, therefore if you try to compress it, you'll find that the compression is ineffective.

Try it. You'll see. It's a very simple experiment -- give it a try.
> 8 votes

# Answer
Always compress first. The goal of encryption is to make data look random and it's impossible to compress random data. Therefore, if you succeed in significantly compressing encrypted data, you need to look for a new encryption algorithm.

If encrypted data doesn't look random, that's a big hint about how to decrypt it. For example, substitution cyphers fail because (assuming the plaintext is ordinary English prose and it's reasonably long) the most common character is almost certain to be the code for E. The next most common characters are almost certain to be the codes for T, A, O and so on.
> 5 votes

# Answer
As well as the other comments, I should point out that the converse is also true.

Encrypted data *should* be incompressible, and hence will be ineffective. However, compressing data before encryption can also make the encryption more secure.

Suppose your plaintext is plain text with a known structure (e.g. MIME, XML, JSON), for example. If an attacker knows that this is what is being encrypted, then it's extremely likely that there are blocks of your plaintext which are known to an attacker. Your cryptosystem is, therefore, vulnerable to a known-plaintext attack. Compressing first makes your "plaintext" look more like random data. If it didn't look like random data, then you could compress it further.

(Of course, this doesn't actually save your cryptosystem from this kind of attack, but it can never make it *more* vulnerable given a proper compression scheme. There are many techniques in modern cryptography where it can't formally be shown that they help security, but it can be shown that they can't hurt. This is one of them.)

In addition, there may be performance advantages. Many modern compression algorithms are faster than modern ciphers, using typical implementations on typical hardware. Compressing first means that there's less data to encrypt. On long messages, this can be a worthwhile tradeoff.

So yes, compress before encrypting.
> 2 votes

---
Tags: data-compression, encryption
---


# Question
Title: What is the best way to index lookups on a 2D array of integers that is boundless in x and y?
Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer).

What is the best way to index these points in order to have an optimised lookup on an arbitrary (x,y) coordinate? Is an O(1) lookup solution possible?

# Answer
Hash map / Hash table (depending on the language used)

Per comments, Some reasoning why: According to Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, the big O of hash tables is O(1) to O(N) for insert, size, and time.

So best case is O(1) solution. If you are able to control the upper and lower bounds, then you have a 'max' number that you could add and can create a table with that in mind.

If you have a 2 by 2, then you can have a table with 4 rows, where the index is the grid coordinate and the value is then the place in memory. Again, language dependent ( this *may* be hard to do in JS, where C would be easy)
> 1 votes

# Answer
For quick look-up on multidimensional points you need to create a R-tree index (http://en.wikipedia.org/wiki/R-tree) or any of its variants (http://en.wikipedia.org/wiki/Spatial\_index#Spatial\_index).

From wikipedia: *R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.*

*The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects.*
> 1 votes

# Answer
Another option is to use an encoding scheme for coordinates like geohash (http://en.wikipedia.org/wiki/Geohash).

From wikipedia: *The main usages of Geohashes are as a unique identifier. represent point data e.g. in databases. Geohashes have also been proposed to be used for geotagging. When used in a database, the structure of geohashed data has two advantages. First, data indexed by geohash will have all points for a given rectangular area in contiguous slices (the number of slices depends on the precision required and the presence of geohash "fault lines"). This is especially useful in database systems where queries on a single index are much easier or faster than multiple-index queries. Second, this index structure can be used for a quick-and-dirty proximity search - the closest points are often among the closest geohashes.*

This scheme can answer nearest point, based on the "geohash" representation of each point. In addition, it is easy to implement and you can find implementations for all programming languages, quite easily.
> 1 votes

# Answer
While there are many spatial hashing methods, I will give you a very simple one, which makes use of 64 bit architectures. Try to concatenate the bits to a 64 bit variable: $z=(x64\<\<32)|y64$, where $x64$ and $y64$ are 64 bit variables obtained by casting your 32 bit variables $x$ and $y$. Then insert them to a fast 64 bit hashtable (such as http://en.wikipedia.org/wiki/MurmurHash). Then in the runtime do the same operation to your queries and look them up from this hashtable. I hope it is clear.
> 0 votes

# Answer
Use a pairing function: http://en.wikipedia.org/wiki/Pairing\_function

You could extend Cantor's pairing function to the integers (it's defined on the naturals) by rotating through the quadrants.
> 0 votes

---
Tags: algorithms, optimization, databases, data-sets
---


# Question
Title: Why Deterministic PDA accepts $\epsilon$ input but DFA not
I was going through a deterministic PDA that accepts $wcw^R$ (described in Ullman's textbook), in which the last transition is given as $(q\_1,\epsilon, Z\_0)\to(q\_2,Z\_0)$, where $q\_2$ is the final state.

In DFAs we don't consider $\epsilon$ transitions, while in PDAs we do include them. Why?

# Answer
There are definitely definitions of DFA that allow $\varepsilon$-transitions. Arguably, they are not very useful for three reasons.

1. They don't add computational power.
2. If you have them, you have to require (for DFA) that every $\varepsilon$-transition is the only transition leaving its source state.
3. Everything you might want to do with them (say, prove closure of regular languages against concatenation) can be done by using NFA and determinising.

Because they *do* have use in proofs, they are usually included in the definition of NFA, though. For example, consider translating regular expressions into NFA.

In PDAs, $\varepsilon$-transitions can be used to deal with stack content without consuming any input. Even in DPDA there can be multiple choices in any given state, depending on stack content. So they are useful here for constructing PDA and are thus usually included in the definition.
> 5 votes

---
Tags: automata, pushdown-automata, nondeterminism
---


# Question
Title: Do the two huffman trees have the same corpus?
Consider the following Huffman trees:

I was asked if those trees can have the same corpus. My answer was no, based on these calculations:

For the right tree:
$a\_1 \le a\_2$
$a\_1 + a\_2 \le a\_5$
$a\_3 \le a\_4$
$a\_1 + a\_2 + a\_5 \le a\_3 + a\_4$

For the left tree:
$a\_1 \le a\_2$
$a\_3 \le a\_4$
$a\_1 + a\_2 + a\_3 + a\_4 \le a\_5$

Adding the last equations from each tree we have that:
$2a\_1 + 2a\_2 \le 0$ Which is a contradiction because frequency cannot be negative.

Nevertheless, I understood that there is a possibility that the two trees would have the same corpus. For instance, consider $1,1,1,2,3$.

So, where do my calculations go wrong?

# Answer
Your inequalities are based on the assumption that the left child of an inner node is not bigger than the right child. However, this does not hold. (Note that the condition is violated for the root of the right tree.)

Instead we do know that whenever the algorith chose to unite two nodes, there were no nodes with smaller weight present. For the left tree we find:

* $a\_1$ ad $a\_2$ were joined before $a\_5$ was joined to another node, so $$a\_1 \leq a\_5\text{ and }a\_2\leq a\_5.$$
* We do not know, if $a\_1$ and $a\_2$ were joined before or after $a\_3$ and $a\_4$, but in case the latter pair was joined first, we find $a\_1 \leq a\_3+a\_4$ and $a\_2\leq a\_3+a\_4$. If the former pair was joined first, we find $a\_1\leq a\_3$, $a\_2\leq a\_3$, $a\_1\leq a\_4$, and $a\_2 \leq a\_4$. These inequalities imply those of the first case, so we can conclude that $$a\_1 \leq a\_3+a\_4 \text{ and } a\_2\leq a\_3+a\_4.$$

Can you go on from here?
> 1 votes

---
Tags: data-structures, trees, information-theory, data-compression
---


title: DCFL substitution closure

text:
# Question
Title: DCFL substitution closure
Deterministic context-free languages are not in general closed under substitution. I have been looking at the DK-test (it is described in the 3rd edition of Sipser's Intro. to Theory of Computation, 2012) which can be used to check if a given CFG is deterministic, and it seems to me this can be used to show that DCFLs are closed under substitution when the substituted languages are disjoint DCFLs. Is this a known result? Or is anything known about the substitution closure of DCFLs with other restrictions on the substituted languages?

# Answer
Since $ab$ is a DCFL, your result would imply that DCFLs are closed under concatenation, which they aren't. So your result can't hold.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: How does one end up with a non-integer exponent in time complexity? (e.g., $O(n^{2.81})$)
Periodically I come across sentences like

"Winograd's variant \[20\] of this algorithm, whose asymptotic complexity is also $O(n^{2.81})$ are considered" (from https://www.cise.ufl.edu/~sahni/papers/strassen.pdf)

I understand intuitively how we end up with complexities like $O(n^2)$ and $O(n \log n)$ because I can see how the loops and trees work. But I've got no idea of how one ends up deriving a complexity with a decimal. Can someone give me an example how this happens?

# Answer
> 9 votes
The running time complexity of Strassen's algorithm is given by the recurrence $$ T(n) = 7T(n/2) + O(n^2). $$ (With a suitable base case.) The solution of this recurrence is $T(n) = O(n^{\log\_2 7})$.

Strassen's algorithm multiplies two $n \times n$ matrices $A,B$ by decomposing them into four $(n/2)\times(n/2)$ matrices each, computing seven linear combinations of the smaller matrices each, say $(A\_i,B\_i)\_{i=1,\dots,7}$, recursively computing $C\_i = A\_i B\_i$, and computing the four $(n/2)\times(n/2)$ matrices of the result by taking linear combinations of the matrices $C\_i$. That's how this running time came to be. If you want to learn more, there is a lot of information out there on Strassen's algorithm. There are, by the way, asymptotically faster algorithms for matrix multiplication, the current champion being Le Gall.

---
Tags: complexity
---


title: Binary counter amortized analysis

text:
# Question
Title: Binary counter amortized analysis
This is a question I have stumbled upon in my textbook, and didn't really know how to approach:

Given a $k$-bit binary counter. We have an operation Increment, which adds 1 to the counter. We add a new operation Decrement, which subtracts 1 from the counter. Prove that the cost for executing $n$ operations is $\Theta(nk)$.

# Answer
> 1 votes
Hint: Think of a value $n$ such that the transition from $n$ to $n+1$ and back is very costly.

---
Tags: algorithms, algorithm-analysis, amortized-analysis
---


# Question
Title: Estimating (c-1) from approximation of c
If we have a FPRAS for approximating the quantity c, can we get another FPRAS for estimating (c-1) using the estimation of c?

# Answer
No. An FPRAS for a function $f$ must return an answer between $(1-\epsilon)f(x)$ and $(1+\epsilon)f(x)$ say 75% of the time. Therefore, if $f(x)=0$, an FPRAS for $f$ must return *exactly* zero, at least 75% of the time: an FPRAS must be able to reliably distinguish zero from non-zero. It does not, however, have to reliably distinguish $y$ from not-$y$ for any $y\neq 0$.

In more detail, suppose we have an FPRAS for a function $f(x)$ and we want to produce an FPRAS for $f(x)-1$. If $f(x)=1$ for some $x$, the FPRAS will give an answer in the range $1\pm\epsilon$, 75% of the time. Just subtracting $1$ from the result of the FPRAS gives an answer within the range $\pm\epsilon$, 75% of the time but an FPRAS for $f(x)-1$ would have to give exactly zero, 75% of the time.
> 2 votes

---
Tags: approximation-algorithms
---


# Question
Title: Hard disk scheduling - N-set-SCAN vs FSCAN
I'm wondering which is a better scheduling algorithm to use. The only real difference I can see is that in FSCAN there are two queues, and when a scan begins all requests are put in one queue and the other left empty. Then during the scan the other queue is used to store new requests and deferred until all the old requests have been processed.

# Answer
> 1 votes
If you take a peek at how real operating systems do it, the answer is that they use algorithms that are orders of magnitude more complex than either.

If I told you the dirty secret behind operating systems (and compiler, and...) text books, I'd have to kill you afterwards.

> Text books only show you the parts where there is some hints of order (some theory behind the algorithms). Most of an operating system's code is battling unruly hardware, work around device bugs, get some half-decent answer out of woefully inadequate data, and do all that fast. Many algorithms are heuristics, derived by trying many ideas, keeping and refining those that worked best. For compilers, the authors of the book describing lcc say that the contents of most compiler books was around 5% of the code of the compiler, and the bug rate in that negligible. I'd say operating systems aren't much different.

---
Tags: scheduling
---


# Question
Title: How do context switches factor into CPU utilization?
When studying operation systems, is context switch time included in CPU utilization time? For example, if 5 percent of CPU time is wasted to context switching, is CPU utilization 95 percent?

# Answer
> 2 votes
What is measured as "CPU utilization" is (time CPU working) / (total time). The overheads (like context switches) are part of the (time CPU working). So you might have 50% CPU utilization, of which 5% is context switch time.

---
Tags: operating-systems, efficiency
---


# Question
Title: Relationship between Las Vegas algorithms and deterministic algorithms
I'm wondering why the following argument doesn't work for showing that the existence of a Las Vegas algorithm also implies the existence of a deterministic algorithm:

Suppose that there is a Las Vegas algorithm $A$ that solves some graph problem $P$, i.e., $A$ takes an $n$-node input graph $G$ as input (I'm assuming the number of edges is $\le n$) and eventually yields a correct output, while terminating within time $T(G)$ with some nonzero probability.

Suppose that there is no deterministic algorithm that solves $P$. Let $A^\rho$ be the deterministic algorithm that is given by running the Las Vegas algorithm $A$ with a fixed bit string $\rho$ as its random string. Let $k=k(n)$ be the number of $n$-node input graphs (with $\le n$ edges). Since there is no deterministic algorithm for $P$, it follows that, for any $\rho$, the deterministic algorithm $A^\rho$ fails on at least one of the $k$ input graphs. Returning to the Las Vegas algorithm $A$, this means that $A$ has a probability of failure of $\ge 1/k$, a contradiction to $A$ being Las Vegas.

# Answer
> 6 votes
There is no contradiction here. A Las Vegas algorithm terminates in expected polynomial time, say $Q(n)$. Markov's inequality shows that for any given polynomial $R(n)$, it terminates in polynomial time $Q(n)R(n)$ with probability $1-1/R(n)$. The number of graphs on $n$ vertices, $k(n)$, is exponential in $n$, so the failure probability $1/R(n)$ is much larger than $1/k(n)$.

Another subtle point is uniformity. A deterministic algorithm needs to handle any input size, while your $A^\rho$ can only handle inputs of certain size. In general, a randomized algorithm can use an unbounded number of random bits. However, your argument can still be formulated in terms of non-uniform models such as circuits, and it is still wrong for the reason described above.

# Answer
> 3 votes
Your algorithm $A^\rho$ has a fixed string of "random" bits, of fixed length $|\rho|$. That means it can only simulate $A$ on inputs that require at most $|\rho|$ random bits to process. If that is all inputs, then you have your deterministic algorithm right there. Otherwise, $A^\rho$ is not a simulation of $A$ on **all** inputs, so it does not solve $P$, as it was claimed to.

# Answer
> 2 votes
There are several subtleties here.

1. The existence of a Las Vegas algorithm *does* imply the existence of a deterministic algorithm: Simply simulate the Las Vegas algorithm on all possible random strings, dovetailing the computation so that they are computed in parallel, until one of the computations return an answer. This doesn't necessarily mean that there is an *efficient* deterministic algorithm, however (e.g. one running not much slower than the expectation of the Las Vegas algorithm).
2. To produce a contradiction, you gave your deterministic algorithm oracle access to a single, fixed random string. This is "deterministic", since the string is fixed, but it is no longer a polynomial-time algorithm because it gets to read this fixed random string. This random string must grow with the size of the input, so essentially you've given your algorithm access to an infinite amount of information. This is what's referred to as a *non-uniform* model of computation -- the algorithm gets some amount of "advice" that is growing in the size of the input. So you would have shown that there is a non-uniform deterministic algorithm running in about the same time as the expected runtime of the algorithm. But you would not have shown that there is a uniform deterministic algorithm.
3. As Yuval points out in his first paragraph, it's ok that, for a fixed random string $\rho$, the algorithm returns "fail" with probability much greater than $1/k(n)$ (with $k(n)$ the number of $n$-node graphs). We just need something like, for each input graph, for "most" random strings $\rho$, we get back an answer.

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


title: string matching vs integer matching

text:
# Question
Title: string matching vs integer matching
How different are string matching and integer matching in terms of time complexity?

I'm asking this especially in relation to Rabin Karp algorithm. Why is it faster to compute hash code for every substring and check for equality of hashcode with the hashcode of the given string than the naive method of just checking if amy of the substrings match with the given string?

# Answer
> 3 votes
Checking whether two 32-bit integers are equal can be done in a single machine instruction.

Checking whether two strings are equal can take a lot longer. If my two strings are each 100 characters long, then checking whether those two strings are equal might require the equivalent of about 100 machine instructions: I have to check them, character by character.

In asymptotic complexity terms: checking equality of (fixed-precision) integers takes $O(1)$ time, checking equality of strings takes $O(n)$, where $n$ denotes the length of each string.

---
Tags: algorithms, strings, substrings
---


# Question
Title: Network Flow with multiple connected subsets
Given a set of buyers, houses, agents with the following constraints:

1. Agents only know a subset of buyers
2. Agents only know a subset of houses
3. Agents can only do some amount of transactions

Construct a flow network to model the problem. *Disclaimer this is homework*

I have put together some thoughts on a solution to this problem. First I realized that agents should be right before the sink node with a max flow equal to the number of possible transactions. This would then limit the number of transactions that can flow through an agent since the max flow can't be exceeded.

I was then thinking that it would be possible to put an edge between each person and house that an agent knows (example if agent knows person A, B and house 1, 2 there are edges (A,1), (A,2), (B,1), (B,2)). Finally, connect each house that an agent knows to an agent with max flow of 1. Then by running a Ford-Fulkerson algorithm across it the inflow of the sink node would indicate max number of transactions.

However, I am concerned that there is no limit of stopping a house from being purchased more than once. I have tried building the network with various configurations (swapping houses and clients, building nodes of client/house pairs) and nothing seems to solve this specific problem.

I am mostly looking for hints to solve this problem.

# Answer
Hint: think about your source node and what it is connected to.
> 1 votes

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


# Question
Title: Does a polynomial-time reduction from A to B imply that B is in NP if A is?
Let f be a polynomial-time reduction of a decision problem A to a decision problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then A $\in$ NP. However, what about the other direction? Assume that A $\in$ NP and consider the following non-deterministic algorithms to decide whether y $\in$ B:

1. "Guess" non-deterministically some x.
2. Verify that f(x) = y by computing f(x) in polynomial time and comparing it with y. If f(x)$\neq$y, reject.
3. Check (using the polynomial-time nRAM for A) whether x $\in$ A and return the answer.

Why does this not qualify as a proof that B $\in$ NP?

# Answer
For your proof to work correctly, $f$ must be surjective:

\begin{align} f: \Sigma\_A^\star \to \Sigma\_B^\star \\ \forall y \in \Sigma\_B^\star \quad \exists x \in \Sigma\_A^\star: f(x) = y \end{align}

Otherwise, you cannot guess a $x$ for each $y \in \Sigma\_B^\star$, with $f(x) = y$ in step 1.

Alghough some polynomial reductions are bijective (e.g. CLIQUE $\le\_p$ INDEPENDENTSET), a polynomial reductions is not required to be either injective or surjective. This is why your proof fails. There are even proofs that use reductions, whose image only consist of two words.

Example for such an extreme case: Proove that $L\_1, L\_2 \subseteq \Sigma^\star$, where $L\_2 \ne \emptyset$ and $L\_2 \ne \Sigma^\star$, both $L\_1$ and $L\_2$ are in $P$ implies that there exists a polynomial reduction from $L\_1$ to $L\_2$.

Let $w\_t \in L\_2$ and $w\_f \in \Sigma^\star \setminus L\_2$. Construct $f: \Sigma^\star \to \Sigma^\star$, such that \begin{align} f(x) = \begin{cases} w\_t & \mbox{if } x \in L\_1\\ w\_f & \mbox{if } x \notin L\_1 \end{cases} \end{align} Since $L\_1$ is in $P$, $f$ simply calls a TM that decides $L\_1$ and then outputs the corresponding words. Therefore, $L\_1 \le\_p L\_2$.
> 2 votes

# Answer
The simple answer to the question in the title is no. By the time hierarchy theorem, we know that **NEXPTIME** $\neq$ **NP** but any problem $A$ in **NP** can be reduced to any **NEXPTIME**-complete problem $B$.
> 0 votes

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


title: Time complexity of a compiler

text:
# Question
Title: Time complexity of a compiler
I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested in LLVM but would be interested in any thoughts people had or places to start research. A quite google seems to bring little to light.

My guess would be that there are some optimisation steps which are exponential, but which have little impact on the actual time. Eg, exponential based on the number are arguments of a function.

From the top of my head, I would say that generating the AST tree would be linear. IR generation would require stepping through the tree while looking up values in ever growing tables, so $O(n^2)$ or $O(n\log n)$. Code generation and linking would be a similar type of operation. Therefore, my guess would be $O(n^2)$, if we removed exponentials of variables which do not realistically grow.

I could be completely wrong though. Does anyone have any thoughts on it?

# Answer
> 53 votes
The best book to answer your question would probably be: Cooper and Torczon, "Engineering a Compiler," 2003. If you have access to a university library you should be able to borrow a copy.

In a production compiler like llvm or gcc the designers make every effort to keep all the algorithms below $O(n^2)$ where $n$ is the size of the input. For some of the analysis for the "optimization" phases this means that you need to use heuristics rather than producing truly optimal code.

The lexer is a finite state machine, so $O(n)$ in the size of the input (in characters) and produces a stream of $O(n)$ tokens that is passed to the parser.

For many compilers for many languages the parser is LALR(1) and thus processes the token stream in time $O(n)$ in the number of input tokens. During parsing you typically have to keep track of a symbol table, but, for many languages, that can be handled with a stack of hash tables ("dictionaries"). Each dictionary access is $O(1)$, but you may occasionally have to walk the stack to look up a symbol. The depth of the stack is $O(s)$ where $s$ is the nesting depth of the scopes. (So in C-like languages, how many layers of curly braces you are inside.)

Then the parse tree is typically "flattened" into a control flow graph. The nodes of the control flow graph might be 3-address instructions (similar to a RISC assembly language), and the size of the control flow graph will typically be linear in the size of the parse tree.

Then a series of redundancy elimination steps are typically applied (common subexpression elimination, loop invariant code motion, constant propagation, ...). (This is often called "optimization" although there is rarely anything optimal about the result, the real goal is to improve the code as much as is possible within the time and space constraints we have placed on the compiler.) Each redundancy elimination step will typically require proofs of some facts about the control flow graph. These proofs are typically done using *data flow analysis*. Most data-flow analyses are designed so that they will converge in $O(d)$ passes over the flow graph where $d$ is (roughly speaking) the loop nesting depth and a pass over the flow graph takes time $O(n)$ where $n$ is the number of 3-address instructions.

For more sophisticated optimizations you might want to do more sophisticated analyses. At this point you start running into tradeoffs. You want your analysis algorithms to take much less than $O(n^2)$ time in the size of the whole-program's flow graph, but this means you need to do without information (and program improving transformations) that might be expensive to prove. A classic example of this is alias analysis, where for some pair of memory writes you would like to prove that the two writes can never target the same memory location. (You might want to do an alias analysis to see if you could move one instruction above the other.) But to get accurate information about aliases you might need to analyze every possible control path through the program, which is exponential in the number of branches in the program (and thus exponential in the number of nodes in the control flow graph.)

Next you get into register allocation. Register allocation can be phrased as a *graph-coloring problem*, and coloring a graph with a minimal number of colors is known to be NP-Hard. So most compilers use some kind of greedy heuristic combined with register spilling with the goal of reducing the number of register spills as best as possible within reasonable time bounds.

Finally you get into code generation. Code generation is typically done a maximal basic-block at a time where a *basic block* is a set of linearly connected control flow graph nodes with a single entry and single exit. This can be reformulated as a graph covering problem where the graph you are trying to cover is the dependence graph of the set of 3-address instructions in the basic block, and you are trying to cover with a set of graphs that represent the available machine instructions. This problem is exponential in the size of the largest basic block (which could, in principle, be the same order as the size of the entire program), so this is again typically done with heuristics where only a small subset of the possible coverings are examined.

# Answer
> 18 votes
Actually, some languages (like C++, Lisp, and D) are Turing-complete at compile time, so compiling them is undecidable in general. For C++, this is because of recursive template instantiation. For Lisp and D, you can execute almost any code at compile time, so you can throw the compiler into an infinite loop if you want.

# Answer
> 6 votes
From my actual experience with C# compiler, I can say that for certain programs the size of the output binary grows exponentially with respect to the size of the input source (this is actually required by the C# spec and cannot be reduced), so time complexity must be at least exponential as well.

The general overload resolution task in C# is known to be NP-hard (and the actual implementation complexity is at least exponential).

A processing of XML documentation comments in C# sources also requires evaluating arbitrary XPath 1.0 expressions at compile-time, that is also exponential, AFAIK.

# Answer
> -1 votes
Measure it with realistic code bases, such as a set of open source projects. If you plot the results as (codeSize,finishTime), then you can plot those graphs. If your data f(x)=y is O(n), then plotting g = f(x)/x should give you a straight line after the data starts to get large.

Plot f(x)/x, f(x)/lg(x), f(x)/(x\*lg(x)), f(x)/(x\*x), etc. The graph will either dive off to zero, increase without bound, or flatten out. This idea comes in handy for situations like measuring insert times starting from an empty database (ie: to look for a 'performance leak' over a long period.).

---
Tags: compilers
---


# Question
Title: Why is Quicksort described as "in-place" if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?
Quicksort is described as "in-place" but using an implementation such as:

```
def sort(array):
    less = []
    equal = []
    greater = []
    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less) + equal + sort(greater)
    else:
        return array

```

You have to create a copy of the list for each recursion. By the first return, in memory we have:

* array
* greater+equal+less

Then by the second recursion across all sub-lists we have:

* array
* greater, equal, less from first recursion
* greater+equal+less from less1, greater+equal+less from greater1

etc...

Is this just badly written code or am I correct in thinking that for a big list, you actually have to have, proportionally, a fair amount of extra space to store thse?

When I think of something that is "in-place", I think of bubble sort, which simply swaps elements in the list like: http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

BubbleSort only requires 1 extra variable to store a potentially swapped element.

# Answer
This particular implementation of quicksort is not in-place. It treats the data structure as a list that can only grow in one direction (in which case a merge sort would be simpler and faster). However, it is possible to write an in-place implementation of quicksort, and this is the way it is usually presented.

In an in-place implementation, instead the sort function is not called recursively on newly constructed arrays that become smaller and smaller, but on bounds that become closer and closer.

```
def sort(array, start, end):
    if end >= start: return
    pivot = array[start]
    middle = start + 1
    for i in range(start+1, end):
        if array[i] >= array[middle]:
            tmp = array[i]
            array[i] = array[middle]
            array[middle] = tmp
            middle += 1
    sort(array, start, middle)
    sort(array, middle, end)

```

(Beware of this code, I have only typed it, not proved it. Any off-by-one errors are yours to fix. Real-world implementations would use a different algorithm for small sizes but this doesn't affect asymptotic behavior. Real-world implementations would choose a better pivot but I won't get into that here as it doesn't really for this question.)

The Wikipedia page presents both a non-in-place and an in-place version of the algorithm.

Quicksort as written here requires $O(d) + s$ extra storage, where $d$ is the depth of the recursion (which depends on the pivot quality) and $s$ is the element size. The stack size requirement can be improved: there are two recursive calls, and we can make the second one a tail call (which consumes no stack). If we always do the recursive call on the smaller half first, then the maximum stack size for array lengths up to $n$ satisfies $\hat S(n) \le \hat S(m)$ with $m \le n/2 \le \hat S(n/2)$, so $\hat S(n) \le \lg\_2(n) \hat S(1)$. Thus we can achieve $O(\log n) + s$ extra storage requirement, regardless of the pivot choice.

There are plenty of other sorting algorithms that can be implemented in-place, including insertion sort, selection sort and heap sort. The simple form of merge sort isn't in-place, but there is a more sophisticated variant which is.

<sub> Thanks to Aryabhata for pointing out that Quicksort can always be done in $\lg(n)$ stack and that there is a variant of merge sort with both $O(1)$ additional storage and $O(n \log(n))$ runtime. </sub>
> 21 votes

# Answer
In addition to Gilles' answer, you can also make Quicksort in-place with your code, if you use linked lists instead of arrays. Just make sure to remove the element from the original list, when appending them to one of the smaller lists.

The following pseudocode assumes/guarantees:

* The first entry in each list (in the following called the head) does not stare an element and allows to keep pointers to the list intact on modifications. `new list` creates a list consisting of a head with `NIL` next-pointer.
* `sort` takes a pointer to a head and returns a pointer to the last element of the sorted list. The pointer given as the argument is also the head of the sorted list.
* The memory location of each element and of the list head remains the same.

.

```
sort(list):
    less_cur = less = new list
    equal_cur = equal = new list
    greater_cur = greater = new list
    if list.next != NIL:
        cur = list.next
        pivot = cur.value
        while cur != NIL:
            list.next = cur.next
            if cur.value < pivot:
                less_cur.next = cur
                less_cur = less_cur.next
            if cur.value == pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            if cur.value > pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            cur = cur.next
        less_cur.next = greater_cur.next = NIL
        less_last = sort(less)
        list.next = less.next
        less_last.next = equal
        greater_last = sort(greater)
        equal_cur.next = greater.next
        return greater_last
    else:
        return list

```

While there is some optimization possible from the above code, this implementation has a greater memory overhead than the array based implementation in Gilles' answer. Additionally it suffers in practice from the problem that linked lists typically are less localized and thus induce a greater number of cache misses than maintaining the same data in an array.

However, this implementation is of advantage, if you have to maintain pointers to the elements through sorting. It is also good to be aware of it, if you are storing your data in a linked list for reasons unrelated to sorting. (If in-place-ness of sorting is of concern, converting between list and array is likely out of question.)
> 3 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: P, Q, ((P→Q)→R) ⊢ R using only modus ponens
Can $R$ be inferred from $P$, $Q$, and $(P \to Q) \to R$ using only modus ponens?
My understanding is that it can, as shown below, but I was told this was incorrect.

Proof of ${P, Q, (P \to Q) \to R} \vdash R$ using modus ponens:

```
P, Q, (P->Q)->R  : Given
Q, (Q)->R        : By Modus Ponens
R                : By Modus Ponens

```

# Answer
> 5 votes
Given $P$, $Q$ and $(P \to Q) \to R$, there is no way to apply modus ponens. You would need to have $(P \to Q)$. If you had $P$, $Q$ and $P \to (Q \to R)$, then you could apply modus ponens twice the way you did, but $P \to (Q \to R)$ and $(P \to Q) \to R$ are different.

$P \to (Q \to R)$ says “if I have P, then if I have Q, then I can get R”.
$(P \to Q) \to R$ says “if I can get Q given P, then I can get R”. It requires a method of getting from P to Q.

It is true that given $P$, $Q$ and $(P \to Q) \to R$, you can deduce $R$. You can see that with truth tables, for example. However this requires logical rules that go beyond modus ponens. This has a mathematical consequence: this deduction is only valid in logics where those extra rules are available (such as classical logic).

There is a computational interpretation of these deductions. $P \to Q$ can be interpreted as a function that produces a $Q$ given a $P$. Modus ponens then comes down to applying a function. Given a function $f : P \to (Q \to R)$, you can apply $f$ to a $P$, which produces a new function $Q \to R$; when you apply this function to a $Q$, you get an $R$. Given a function $g : (P \to Q) \to R$, the situation is different: you need a function from $P$ to $Q$ to get started. Given a $Q$, it's easy: you can use a constant function that returns this $Q$. But that first step of constructing the constant function is not modus ponens.

# Answer
> 1 votes
No, you can't get $R$ using only modus ponens. Your second line is incorrect. If we knew $P \to Q$, then from that and $(P \to Q) \to R$ you could get $R$. But you can't get $Q \to R$ from $P$ and $(P \to Q) \to R$ using modus ponens (maybe with some other rule, but not modus ponens alone).

---
Tags: logic, propositional-logic
---


# Question
Title: What does superscript + mean in relational algebra?
What does superscript + mean in relational algebra? Suppose $A$ is a subset of attributes of all attributes in a relation $R$. What does $A^+$ mean?

# Answer
I got the answer. $A^+$ represents the set of attributes that $A$ functionally determines.
> 1 votes

---
Tags: relational-algebra, notation
---


title: Proof of sum of powerset?

text:
# Question
Title: Proof of sum of powerset?
Is there already a worst case time complexity proof for the sum of all elements in a power set? I would assume, naively, you have to just add everything, which would run in about 2^n, where n is the size of the set.

For example: A = {1,2,3} Powerset(A) = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3} } Sum(Powerset(A)) = {{} + {1} + {2} + {1 + 2} + {3} + {1 + 3} + {2 + 3} + {1 + 2 + 3} }

I'm defining addition between sets as: A = {1}, B = {2,3}, A + B = {1} + {2 + 3} = 6

# Answer
> 3 votes
Hint: If I understand you correctly, you are after $$ \sum\_{B \subseteq A} \sum\_{x \in B} x. $$ Try reversing the order of summation: $$ \sum\_{B \subseteq A} \sum\_{x \in B} x = \sum\_{x \in A} \sum\_? x, $$ where $?$ is some condition that you will have to come up with. See if that helps you to find a closed formula for the original double sum.

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


# Question
Title: Meyniel's theorem + finding a Hamiltonian path for a specific graph family
Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want to find a Hamiltonian path in it (from any vertex to any other vertex, I don't care where to start or stop).

I wanted to refer to Meylien's theorem for this:

> A strongly connected simple directed graph with $n$ vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to $2n − 1.$

There are two subtleties that I'm not sure about with this theorem:

* What is meant by "adjcent vertices". Does the order matter here? Is the pair $(v,w)$ adjacent even if $(w,v) \in E$ but not $(v,w)$ itself? If that is the case and the graph is strongly connected, than it must obviously be Hamiltonian, since there are no non-adjacent pairs of vertices at all.
* A graph with the above property is not necessarily strongly connected. I think this is easy to solve: We can just decompose the graph into SCCs. We will still have no non-adjacent pairs of vertices in the components and all of them are Hamiltonian. We can then construct a Hamiltonian path of the whole graph by connecting them in topological order.

Is the above reasoning correct and the theorem applicable? Or is there some other argument we can use to show that there is a Hamiltonian path in the graph?

In the end I want to actually *find* the Hamiltonian cycles in the SCCs, but haven't had much luck finding a constructive proof of the theorem, let alone an algorithm that solves this. Can it be done in a straightforward way? I feel like some kind of greedy approach could work, where we take the nodes in decreasing order of outdegree or something similar.

# Answer
It is enough to prove your claim for the case of a *tournament*, in which for every pair of vertices $v\neq w$, exactly one of the edges $(v,w),(w,v)$ is in the graph. Wikipedia has an algorithmic proof that every such graph has a Hamiltonian path. If the tournament is strongly connected, it has a Hamiltonian cycle.
> 3 votes

---
Tags: algorithms, graphs, hamiltonian-path
---


# Question
Title: Runtime bounds on algorithms of NP complete problems assuming P≠NP
Assume $P\neq NP$.

What can we say about the runtime bounds of all NP-complete problems?

i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal algorithm for **any** NP-complete problem runs in time of at least $\omega(L(n))$ and at most $o(U(n))$ on a input of length $n$?

Obviously, $\forall c:L(n)=\Omega(n^c)$. Also, $U(n) = O(2^{n^{\omega(1)}})$.

## Without assuming $QP\neq NP$, $ETH$, or any other assumption which is not implied by $P\neq NP$, can we give any better bounds on $L,U$?

**EDIT:**

Note that at least one of $L,U$ has to be far from the bounds I gave here, since being NPC problems, these problems has poly time reduction between each other, meaning that if some NPC problem has an optimal algorithm of time $f(n)$, then all problems has an algorithm (optimal or not) of runtime $O(f(n^{O(1)}))$.

# Answer
> 2 votes
My interpretation of the question is that is asks about the possibilities in *relativized worlds*. Suppose that in some relativized world, $P \neq NP$. Can we deduce anything non-trivial about the time complexity of NP-complete problems? The Baker–Gill–Solovay argument shows that we can "force" some NP problem to require exponential time, so the upper bound given in the question is essentially optimal.

Regarding the lower bound, we sketch below a proof that relative to some oracle, $NP = \mathrm{TIME}(2^{O(\log^2 n)})$. Assuming that the sketched proof is correct, we can also apply it to functions smaller than $2^{O(\log^2 n)}$, and this shows that the lower bound given in the question is also essentially tight.

**Proof sketch.** We construct two oracles $O\_1,O\_2$: the first behaves like a $\mathrm{TIME}(2^{O(\log^2 n)})$-complete problem, and the second implements the Baker–Gill–Solovay diagonalization. It is straightforward to pack both oracles into a single oracle.

The oracle $O\_1$ consists of all pairs $\langle M, x \rangle$ such that $M$ is an oracle Turing machine that accepts $x$ in running time $2^{2^{\sqrt{\log |x|}}}$ when given access to the oracles $O\_1,O\_2$ restricted to inputs of length at most $2^{\sqrt{\log |x|}}$. (This is not a circular definition.)

The oracle $O\_2$ is defined in the same way that the oracle is defined in Baker–Gill–Solovay: for each clocked oracle Turing machine $M$ running in time $T = 2^{o(\log^2 n)}$, we find some input length $n$ which is "untouched", run $M$ on $1^n$ for $T$ steps, and for each query to $O\_2$ of size $n$, we mark that this input is not in $O\_2$ (for other queries we also mark that the input is not there, unless we had already decided that it is in $O\_2$). Queries to $O\_1$ are handled similarly (as implicit queries to $O\_1,O\_2$ of smaller size, handled recursively); notice that such queries never mention strings of length $n$ in $O\_2$, since $2^{\sqrt{\log T}} \< n$. If the machine accepts, we mark all other strings of length $n$ in $O\_2$ as missing, otherwise we pick some string of length $n$ and put it in $O\_2$.

The class $P^{O\_1,O\_2}$ consists of all programs running in time $2^{2^{O(\sqrt{\log n})}}$, making queries to $O\_1,O\_2$ of size $2^{O(\sqrt{\log n})}$. The class $NP^{O\_1,O\_2}$ is of the form $x \mapsto \exists |y|\<n^C \varphi(x,y)$, where $\varphi \in P^{O\_1,O\_2}$, and so it is contained in the class of all programs running in time $2^{n^C}$ and making oracle queries of size $2^{O(\sqrt{\log n})}$. The latter is contained in $\mathrm{TIME}(2^{\log^2 n^C})^{O\_1,O\_2}$, since we can use $O\_1$ to decide it. This shows that $NP^{O\_1,O\_2} \subseteq \mathrm{TIME}(2^{O(\log^2 n)})^{O\_1,O\_2}$.

For the other direction, let $L$ be the language which consists of $1^n$ for each $n$ such that $O\_2$ contains some string of length $n$. By construction of $O\_2$, $L \notin \mathrm{TIME}(2^{o(\log^2 n)})^{O\_1,O\_2}$, while clearly $L \in NP^{O\_1,O\_2}$. This shows that $NP^{O\_1,O\_2} = \mathrm{TIME}(2^{O(\log^2 n)})^{O\_1,O\_2}$.

---
Tags: complexity-theory, time-complexity, np-complete, p-vs-np
---


# Question
Title: Why is it important for functions to be anonymous in lambda calculus?
I was watching the lecture by Jim Weirich, titled 'Adventures in Functional Programming'. In this lecture, he introduces the concept of Y-combinators, which essentially finds the fixed point for higher order functions.

One of the motivations, as he mentions it, is to be able to express recursive functions using lambda calculus so that the theory by Church (anything that is effectively computable can be computed using lambda calculus) stays.

The problem is that a function cannot call itself simply so, because lambda calculus does not allow named functions, i.e.,

$$n(x, y) = x + y$$

cannot bear the name '$n$', it must be defined anonymously:

$$(x, y) \rightarrow x + y $$

Why is it important for lambda calculus to have functions that are not named? What principle is violated if there are named functions? Or is it that I just misunderstood jim's video?

# Answer
The main theorem regarding this issue is due to a British mathematician from the end of the 16th century, called William Shakespeare. His best known paper on the subject is entitled "Romeo and Juliet" was published in 1597, though the research work was conducted a few years earlier, inspired but such precursors as Arthur Brooke and William Painter.

His main result, stated in Act II. Scene II, is the famous theorem:

> What's in a name? that which we call a rose
> By any other name would smell as sweet;

This theorem can be intuively understood as "names do not contribute to meaning".

The greater part of the paper is devoted to an example complementing the theorem and showing that, even though names contribute no meaning, they are the source of endless problems.

As pointed out by Shakespeare, names can be changed without changing meaning, an operation that was later called $\alpha$-conversion by Alonzo Church and his followers. As a consequence, it is not necessarily simple to determine what is denoted by a name. This raises a variety of issues such as developing a concept of environment where the name-meaning association are specified, and rules to know what is the current environment when you try to determine the meaning associated with a name. This baffled computer scientists for a while, giving rise to technical difficulties such as the infamous Funarg problem. Environments remain an issue in some popular programming languages, but it is generally considered physically unsafe to be more specific, almost as lethal as the example worked out by Shakespeare in his paper.

This issue is also close to the problems raised in formal language theory, when alphabets and formal systems have to be defined up to an isomorphism, so as to underscore that the symbols of the alphabets are abstract entities, independent of how they "materialize" as elements from some set.

This major result by Shakespeare shows also that science was then diverging from magic and religion, where a being or a meaning may have a true name.

The conclusion of all this is that for theoretical work, it is often more convenient not to be encumbered by names, even though it may feel simpler for practical work and everyday life. But recall that not everyone called Mom is your mother.

**Note**:
The issue was addressed more recently by the 20th century American logician Gertrude Stein. However, her mathematician colleagues are still pondering the precise technical implications of her main theorem:

> Rose is a rose is a rose is a rose.

published in 1913 in a short communication entitled "Sacred Emily".
> 28 votes

# Answer
I would like to venture an opinion that is different from those of @babou and @YuvalFilmus: It is **vital** for pure $\lambda$-calculus to have anonymous functions. The problem with having only named functions is that you need to know in advance how many names you will need. But in the pure $\lambda$-calculus you have no a priori bound on the number of functions used (think about recursion), so you either use (1) anonymous functions, or (2) you go the $\pi$-calculus route and provide a fresh name combinator ($\nu x.P$ in $\pi$-calculus) that gives an inexhaustible supply of fresh names at run-time.

The reason pure $\lambda$-calculus does not have an explicit mechanism for recursion is that pure $\lambda$-calculus was originally intended to be a foundation of mathematics by A. Church, and recursion makes such a foundation trivially unsound. So it came as a shock when Stephen Kleene and J. B. Rosser discovered that pure $\lambda$-calculus is unsuitable as a foundation of mathematics (Kleene–Rosser paradox). Haskell Curry analysed the Kleene-Rosser paradox and realised that its essence is what we now know as Y-Combinator.

Added after @babou's comment: there is nothing wrong with having named functions. You can do this as follows: $\mathsf{let} f = M \mathsf{in} N$ is a shorthand for $ (\lambda f.N)M $ in the call-by-value $\lambda$-calculus.
> 10 votes

# Answer
I believe the idea is that names are not necessary. Anything that appears to require names can be written as anonymous functions.

You can think of the lambda calculus like assembly language. Someone in a lecture on assembly might say "There are no object oriented inheritance trees in assembly language." You might then think up a clever way to implement inheritance trees, but thats not the point. The point is that inheritance trees are not required at the most basic level of how a physical computer is programed.

In the lambda calculus the point is that names are not required to describe an algorithm at the most basic level.
> 4 votes

# Answer
I'm enjoying the 3 answers here so far -- most especially @babou's Shakespearen analysis -- but they don't shed light on what I think is the essence of the question.

λ-calculus does bind names to functions whenever you apply a function to a function. The issue is not the lack of names.

*"The problem is that a function cannot call itself simply" by referring to its name.*

(In pure Lisp, the name --\> function binding is not in scope within the function's body. For a function to call itself by its name, the function would have to refer to an environment that refers to the function. Pure Lisp has no cyclic data structures. Impure Lisp does it by mutating the environment that the function refers to.)

As @MartinBerger pointed out, the historical reason that λ-calculus doesn't let a function call itself by name was an attempt to rule out Curry's paradox when trying to use λ-calculus as a foundation of mathematics, including deductive logic. This didn't work since techniques like the Y combinator allow recursion even without self-reference.

From Wikipedia:

> If we can define function `r = (λ.x x x ⇒ y)` then `r r = (r r ⇒ y)`.
>
> If `r r` is true then `y` is true. If `r r` is false then `r r ⇒ y` is true, which is a contradiction. So `y` is true and as `y` can be any statement, any statement may be proved true.
>
> `r r` is a non-terminating computation. Considered as logic `r r` is an expression for a value that does not exist.
> 4 votes

---
Tags: lambda-calculus, functional-programming
---


title: Pumping lemma not regular

text:
# Question
Title: Pumping lemma not regular
How would about proving this is not regular with the pumping lemma. Please include all steps and explain all steps. I am really new with this.

$1^{2x}0^y$ and $y\>= x$

Does it matter which side you pump? How do you pick which side to pump?

This is what I was thinking:

$$u = 1^{2x}$$ $$v = 0^y$$ $$w = 1^{2x}0^y$$

Am I on the right track? What else do I need to do?

# Answer
assuming you have a pump length $p$ then there is a string $1^{2x}0^y$ with $p \lt x \le y$ as part part of the language

thus the partition $uvw$ with $\text{length}(uv)\<p$ must have $uv$ as all $1$s

this means that your pump string $v$ contains all $1$ which if pumped can create twice as many $1$ than $0$s which is not part of the language. QED
> 0 votes

---
Tags: pumping-lemma
---


title: Kleene Star Property : L*L* = L*

text:
# Question
Title: Kleene Star Property : L*L* = L*
I am trying to prove this expression but don't have an exact idea about what to do:

If $E$ is any alphabet and $L$ is any language $L \subseteq E^\*$. Prove that $L^\*L^\* = L^\*$.

# Answer
> 4 votes
The standard approach to such proofs is:

1. Let $w \in L^\*L^\*$. This implies \[...\] and thus $w \in L^\*$.
2. Let $w \in L^\*$. This implies \[...\] and thus $w \in L^\*L^\*$.

Both parts combined give the proof of your statement. Does this help?

---
Tags: formal-languages
---


# Question
Title: Maximum number of matched vertexes in a one-to-many bipartite graph
I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who are satisfied. A bidder is satisfied if he gets all the items that he bid for in the first place. For eg-

```
Bidders = A,B,C
Items = 1,2,3,4

Bidder    Bids
A         1,2
B         2,3
C         3,4

```

In this case its only possible to satisfy 2 bidders at max.

I've tried to model the problem to a maxflow problem and have taken several approaches but to no avail My approaches so far-

1. Tried to model this problem as a bipartite matching problem. The only problem being that instead of a one-one mapping I have a one-many mapping with an AND condition.
2. A maxflow problem with edges going from source to each vertex with a capacity of number of bids. Problem here being ensuring that all edges from a bidder are selcted.
3. A maxflow problem with both upper bounded and lower bounded edge capacities.

# Answer
Since your problem is exactly the **set packing problem**, it is NP-hard. However, you only have $n = 20$ bidders, so you can solve it using a simple exponential algorithm:

1. For every item $i$, build the subset $B\_i$ of bidders that bid for it. You can represent this subset for example as a bitmask. You know that for all $i$, every subset $S \subset B\_i$ with $|S| \> 1$ can not be a subset of the solution.
2. For all $B\_i$, enumerate all of its "forbidden" subsets of size \> 1 and store them. Avoid revisiting already stored subsets by using recursion and memoization, by canceling the bits one after another.
3. Go through all subsets of bidders. For every set, check whether it has a a forbidden subset. You can use the same recursive algorithm as in step 2.

Note that if you only enumerate subsets of size 2 in step 2, you have reduced your problem to an independent set problem in a graph with $n$ nodes, so you can apply any other more efficient algorithm to it.

Runtime: $O(n \cdot (2^n + m))$, with $m$ being the number of items and $n$ being the number of bidders. With a good independent set algorithm you can get something like $O(m \cdot n^2 + 1.3^n)$
> 2 votes

# Answer
This problem can be reduced to the **maximum independent set problem**:

We use the fact that if $A$ and $B$ bid for the same item, then $A$ can be satisfied if and only if $B$ is not satisfied, and thus we construct a new graph:

The vertex set $V$ represents all the bidders, and we connect with an edge any pair of bidders that have **any** common bid.

Note that this is a general graph, and it's not bounded in any way (we can create any general graph with the input of your problem)

The maximum independent set in this graph represents maximum number of satisfied bidders. In order to get the actual matching, you can save the list of wanted items in each vertex, and translate the maximum independent set to a matching.

Unfortunately this problem is $NP-Hard$, but many good approximation algorithms and heuristics are available.
> 1 votes

# Answer
Ron Teller's answer is probably the best, but here is one additional way you could try to solve it in practice: you could formulate this as a zero-or-one integer linear program.

In particular, introduce one (zero-or-one integer) unknown $x\_i$ for each bidder, where $x\_i=1$ means that bidder $i$ gets all his items and $x\_i=0$ means that bidder $i$ doesn't get anything. Now you can formulate the requirement that no item is chosen by more than one bidder as follows: if bidder $i$ and $j$ both require the same element, introduce the constraint $x\_i + x\_j \le 1$. Finally, your objective function is the sum of the $x\_i$'s, and you want to maximize this. You could feed this to an off-the-shelf ILP solver, and see how it does. With only 20 bidders, my guess is that they will solve this kind of problem easily.

Of course, with only 20 bidders, another feasible solution is to simply enumerate all possible subsets of the 20 bidders, and check which ones satisfy your constraints. There are only one million of them, so this is probably viable... However, the ILP solution will probably scale better.
> 1 votes

---
Tags: algorithms, graphs, network-flow, bipartite-matching, max-cut
---


title: ALL_{REGEX} in PSPACE algorithm

text:
# Question
Title: ALL_{REGEX} in PSPACE algorithm
$ALL\_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^\*$. In a proof for $ALL\_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ on regular expression $R$ is given

Convert R to an NFA $N = (Q,\Sigma,\delta,S,F)$; $K = S$;

While $K \cap F \neq \emptyset$

1. Non-deterministically guess a character $a \in \Sigma$
2. S' = Compute the new set of states from character $a$ and states $K$
3. K = S'

The proof states that iff $M$ does not halt, then $L(R) = \Sigma^\*$. Suppose we have $\Sigma = \\{a,b\\}$ and R = a\*. Why doesn't this machine halt? Won't there be a single path of guesses (namely, a\*) that goes on forever, implying the whole machine does as well?

The algorithm goes prove that after $2^{|Q|}$ steps, we know the language must be $\Sigma^\*$, so we accept instead of looping. I understand the intuition of the algorithm and how it would be implemented deterministically , but I'm confused as to how the algorithm above works when the NTM formalism accepts if any path accepts and it is making me question my understanding of NTMs.

# Answer
The idea is that if a DFA having $n$ states isn't universal (doesn't accept $\Sigma^\*$) then there must be some word of length at most $n$ which it doesn't accept. The proof is similar to the proof of the pumping lemma: take any word not accepted by the DFA, and trace its route through the DFA. You can always shorten it to a word which ends up in the same state, and additionally all states encountered are *distinct*. Since there are only $n$ distinct states, this finished up the proof.

An NFA having $n$ states is equivalent, via the powerset construction, to a DFA having $2^n$ states. Therefore if it is not universal then it rejects some word of length at most $2^n$. The non-deterministic algorithm you describe guesses such a word and verifies that it is indeed rejected by the NFA. Since NPSPACE=PSPACE, we can convert this into a deterministic algorithm (in fact, one using space $O(n^2)$).
> 2 votes

---
Tags: turing-machines, space-complexity
---


# Question
Title: What is the difference between bounding and pruning in branch-and-bound algorithms?
Could anybody please explain what the difference between "bounding" and "pruning" in branch and bound algorithms is?

I'd also appreciate references (preferably books), where this distinction is made clear.

# Answer
Both, branch and bound and pruning, are techniques used to reduce the number of possible solutions one has to examine when a search tree is there.

**Pruning** is the act of removing whole branches from the tree that cannot fulfill **constraints**. Problems, where solutions might apply pruning are:

**Branch and bound** is used to find **optimal** solutions. You also remove whole branches in branch and bound.

When you have found a solution, this solution has a value. Let's say you're interested in maximinzing that value. This means, as soon as you have found a solution of value $X$, you can remove all branches that cannot get a higher value than $X$. So you have a lower bound for the solution and you can prune all branches that do not fulfill this constraint.

Problems, where solutions might use branch and bound are:
> 4 votes

# Answer
In branch and bound algorithms, you essentially partition the original problem to be solved in a number of subproblems whose union is equivalent to the original problem you started with. The process of deriving new subproblems is called branching and leads to the so-called branch decision tree. Now, when you need to solve a subproblem, you can either determine its optimal solution, show that the subproblem is infeasible (so that you can discard it), or you can show that the subproblem solution is no better than the best known solution for the original problem. If you are not able to solve a subproblem, you branch again, partitioning it into sub-subproblems. Now, for each subproblem you can derive a lower bound for its solution and, if the lower bound is greater than or equal to the best known solution for the original problem, you can discard the subproblem since the best solution you can obtain for the subproblem is certainly worst with regard to the feasible solution of the original problem. In order to get a lower bound you must relax the problem. The relaxation may be continuous, lagrangian etc.

Therefore, the word bound in branch and bound refers to the process of determining lower bounds for subproblems. Pruning refers instead to the process of discarding subtrees in the branch decision tree rooted at subproblems whose solution is impossible or worst with regard to the feasible solution of the original problem.
> 12 votes

# Answer
As I understand it pruning is used in contraint programming problems where you are interested in finding a feasible solution as opposed to bounding where you are interested in an optimal solution, i.e. some maximum or minimum of an object function.
Take for example the 8-Queens puzzle, you branch by setting the first queen thereby decomposing the original problem into subproblems, since you are given a set of constraint the placing of the queen eliminates a number of solutions that have become infeasible (you are no longer able to place any other queens on the same row or diagonals) thereby reducing the search space.
As Massimo Cafaro explained above bounding is used to reduce the search space by providing an upper or lower bound. If however you are trying to find a feasible solution to a problem you reduce the search space by propagating the constraints through branching, if you exhaust the search space without finding a feasible solution you can backtrack and try a different configuration.
I hope I haven't confused anyone with this explanation and I do not contradict the above answer, however I think the answer aimed at the difference between pruning and bounding qua ways of reducing the search space of a given problem.
> 3 votes

---
Tags: algorithms, terminology, branch-and-bound
---


# Question
Title: Number of edges required to guarantee $K_3$ as subgraph
I am trying to solve a given problem: Find an algorithm to determine if a graph has a clique of size 3 in $O(n^{2.81})$ steps. The hint given is that $2.81 \> \log 7$. In order to solve this I came up with a conjecture: if $m \> n^{\log 7}$ then the graph has $K\_3$ as a subgraph. This will easily solve the problem if the conjecture is true.

I am trying to argue by contradiction: Let $m \> n^{\log 7}$ and assume there does not exist a $K\_3$ subgraph. Then for any set of three vertices there are exactly 7 choices for how to connect them. However, I am stuck as to how to progress from here.

Does anyone see a way to prove this, or if the conjecture is even true. I'm also interested to see if the conjecture can be extended, i.e. if $m \> n^{\log 2^k -1})$ does there exist a $K\_k$ subgraph?

# Answer
Hint: Matrix multiplication runs in time $O(n^{2.71})$. A relevant matrix is the adjacency matrix of the graph.

*Actually, this has been improved several times in the past very. Recently, Le Gall improved this to time $O(n^{2.3728639})$. It is conjectured that matrix multiplication runs in time $O(n^{2+\epsilon})$ for every $\epsilon \> 0$.*
> 4 votes

---
Tags: graphs
---


# Question
Title: Can Turing Machines decide on computability?
Can a Turing Machine decide whether an arbitrary real number is computable or not? Does this even follow from the solution of the Halting problem? If not, who proved it?

# Answer
> 8 votes
A real number cannot be input into a Turing machine, since it is an infinite object. There are various models for providing a Turing machine with oracle access to real numbers, but these are by definition computable.

You could imagine a Turing machine given a ZFC definition of a real number, and in that case it's undecidable. For example, given a Turing machine $T$, you could define a number $x$ as follows: if $T$ doesn't halt in $n$ steps then the $n$th bit of $x$ is zero. Otherwise, it is the $n$th bit of Chaitin's constant. So $x$ is computable if and only if $T$ never halts.

---
Tags: computability, turing-machines, real-numbers
---


# Question
Title: Why can't I run a mac program natively on windows?
Basically, I believe that if you have something like a .dmg file the OS opens it with a certain program which takes the code behind it and does things to it. So why couldn't you then take the program that runs the .dmg file on Mac and put it on window to run the program? I know I'm probably missing some key component here that makes me wrong but I have no idea what; I'm a bit of a noob to so take it easy on me.

# Answer
Think of the `.dmg` file as a book of short stories.

Windows and Mac OS X have different formats of books, so the gesture to open one is a bit different (think of pages turned from left to right or right to left). Less metaphorically, a `.dmg` file packs a bunch of files, and the format in which these files are packed isn't one that Windows supports natively. However it would be easy to write a program to unpack `.dmg` files on Windows, and I'm sure someone has done so.

Ok, now you have the book open and can see the pages. That doesn't necessarily mean you can read it, though. Let's say you speak English and only English… but the book is in Turkish. You aren't going to be able to understand a word of it.

A computer program contains a bunch of elementary instructions. The instruction set is like the script that the book is written in. The instruction set is determined by the type of processor that powers the computer. Modern Macs and Windows PCs have the same type of processor (one of the two x86 families, either the 32-bit one or the 64-bit one). So that step is fine — you can make out the individual letters. However, that's not enough!

Some instructions rely only on the processor: instructions like “read the value at this memory location” or “add these two numbers” or “jump to this location in the program”. However, every time the program wants to interact with something else (access a disk file, read user input, display something, communicate over the network, etc.), the program makes a call to the operating system. And two completely different operating systems, such as Windows and Mac OS X, have completely different APIs — they offer completely different system calls. (Note that the metaphor breaks down somewhat here: the problem isn't that the arrangement of instructions has to be different, but that a few very important instructions have radically different effects.)

There's even another layer of differences: Windows and OSX even have different executable file formats (PE vs Mach-O). The executable format determines how code and data are arranged in the file and how things like dependencies on libraries are represented. Making Windows understand OSX's file format would require some work, but making Windows understand OSX's system calls would be a Herculean task.

You can't read the book because it's in Turkish. You could learn Turkish, but it would take years of effort. Similarly, making Windows able to run OSX programs would take a huge amount of programming effort.

In fact, it's simpler to simulate a processor with its peripherals, by implementing all of its instructions, than it is to simulate an operating system by implementing all of its system calls. This is called a virtual machine. You can run an operating system on an emulated machine that is in fact provided by a program running under another operating system. For example, you can run OSX on an x86 CPU emulated by Vmware which is running as a Windows application. (In the specific case of OSX, this is difficult, but not for technical reasons, rather because Apple makes it difficult for commercial reasons.)
> 13 votes

# Answer
Long story short - they are two different Operating Systems (OSes).

You probably think of an OS as the way a computer looks (the GUI) and what applications it comes with but an OS is a lot more than that. When a programmer wants to do something like display a single letter on the screen in their application it can actually be pretty complicated. For example when a PC is in text mode (what happens right before you seen the Windows loading screen) a program run at that time would have to write a letter to memory address 0xB8000. Why? Because video cards use memory based IO to allow programs to write to the screen. Not only is this really technical for you but it requires more hardware knowledge than most programmers have. Not only that but to make the same program do the same thing on a different type of computer where the video cards worked differently the programmer would have to know all about how the hardware worked on that system.

To make it so programmers could create applications without knowing a lot about the hardware one of the things that was created was an Operating System. Instead of trying to talk to the hardware directly a programmer will now ask the OS, "Hey OS can you display this text on the screen for me?". This is what is called a "system call". Part of the problem is that each OS and a completely different set of system calls which keeps a programmer from having to know about the hardware but makes them still have to learn how to ask each OS to do things.

So they tried to make a standard set of helper routines (libraries) that would work in all OSes. Think of it as a translator, a program asks the helper routine to print a formatted string (printf) which in turn actually converts that to the OS specific routine (probably called something like sprintf). This portable layer is called POSIX which you can read more about at https://en.wikipedia.org/wiki/POSIX. But as computers grew more powerful (for example the added the ability to display graphics where before they were only text based) the Operating Systems added more libraries for the applications to call which were not covered in the POSIX standard so developers that didn't want to reinvent the wheel by recreating all the features in an OS just ask the OS to do things which makes their application only work on a particular OS.

There is a little bit more to it than that (different file formats for executables, etc) but the libraries that an OS provides to an application and the underlying CPU types is really what make it difficult to copy applications over.

Sometimes you have the same OS (or close enough - the libraries are the same) but you have completely different CPUs. This can also cause problems. For example right now you can go get a Windows RT tablet. The "RT" tablet can not run normal Windows programs, even those that work on other Windows tablets. This is because they use a different CPU architecture. A CPU is the brain of the computer that does the majority of the work. The primary job of a programmer is to create instructions for a CPU. But it turns out this is really really hard. To make it easier they created something called a compiler. What a compiler does is it allows a programmer to write CPU instructions in something that almost looks like english (a high-level programming language) and it converts the almost-english text into the really hard to understand stuff that the CPU actually needs (opcodes) in order to know what to do. Basically the compiler is another type of translator that keeps programmers from having to know a lot of detail about the hardware (CPU in this case).

The problem here is that the output of the compiler is specific to a family of CPUs. Compiler output meant for Intel CPUs (Most PCs) won't work on ARM CPUs (Most tablets and phones).

All these translation layers help programmers worry less about the low-level details and focus more on the high-level logic or behavior of an application. As more translation layers and helper libraries (off the shelf functionality that doesn't need to be recreated) have been created they have enabled programmers to create more feature-full applications. The problem is since the applications they create have so many dependencies and are translated into CPU and OS specific stuff their applications become none-portable. Sometimes a developer takes the time to make sure their application will work on multiple types of CPUs and OSes, this is called porting.
> 5 votes

---
Tags: operating-systems
---


# Question
Title: What's flawed about the "save-the-input" method of reversible computing?
I'm an undergraduate just beginning to read about reversible computing. I know that, because of Landauer's principle, irreversible computations dissipate heat (and reversible ones do not). I brought it up with my professor, who had never heard of reversible computing before, and he was having difficulty understanding why the theory of reversible computing was not trivial.

His point was just that you can always save the input, i.e. for any function $f: \\{ 0, 1 \\}^n \rightarrow \\{ 0, 1 \\}^n$ that you wish to make reversible, define a new function $f\_{reversible}: \\{ 0, 1 \\}^n \rightarrow \\{0, 1 \\}^{2n}$ (or $\\{ 0, 1 \\}^{2n} \rightarrow \\{0, 1 \\}^{2n}$ and you just put $0$s in for the last $n$ bits of the input) which returns the output in the first $n$ bits and the input in the other $n$ bits. Then in order to invert $f\_{reversible}$ you just discard the output and return the input that you saved.

My immediate objection was that this takes more memory than the original function did -- though only by a constant factor. Constraining the output to $n$ bits would seem to restore the interesting-ness of the problem, though. Is this what is usually meant by reversible computing?

Another objection seemed to be that when we discard the output, we're doing something irreversible which is going to dissipate heat. But we correctly recovered the initial state, so how could it be irreversible? I don't know enough physics to understand whether the important thing w/r/t heat is just for the entire computation to be reversible, or whether every step needs to be reversible as well, or if this idea is just up the wrong tree.

# Answer
There are two important features of reversible computing that are missing from your discussion of reversible computing:

1. A reversible function has to be a bijection, and
2. Reversibility is defined on the level of local gates, not just the global level.

In particular, for your extension of $\\{0,1\\}^n \rightarrow \\{0,1\\}^n$ into $\\{0,1\\}^{2n} \rightarrow \\{0,1\\}^{2n}$ by copying, you don't ensure bijection because you don't explain what happens when the last $n$ bits of input for your function aren't $0^n$.

As for the second point, that is really the essential part of reversible-computing from the physics perspective. The physical process can't simply "undo" heating at a global level, thus every gate has to be reversible for the circuit to be reversible in the relevant-to-physics sense.

Finally, the theory of reversible computing is not unreasonably complicated, but it is definitely not trivial. In particular, there are some circuits that can be implemented with strictly fewer registers/wires non-reversibly than they can be reversibly. However, the blow up in going from non-reversible to reversible is not too bad.

In general, I seldom hear reversible computing come up in classical CS courses, because it is seldom relevant to classical computation. However, it is an important topic in quantum computing because all quantum circuits are reversible and because one has to handle what is on your 'junk' wires carefully to avoid unnecessary entanglement.
> 12 votes

---
Tags: computability, reversible-computing
---


# Question
Title: Minimizing the following objective function with matrices
I am trying to work out centrality in a network using Freeman's network centrality. I have an in degree of 83 and an out degree of 110. I want to work out the network centrality using my out degree using the following formula: $$ \frac{\sum\_{i=1}^{g}\[{C}^d ({n\*})-C^{d}\]} {\[(N-1)(N-2)\]} $$

This is where $$ {n} $$ is node in my graph and presuming the out- degree. Any suggestions on how to apply this formula?

Thanks in advance!

# Answer
> 1 votes
Freeman's network centrality is a measure of a network (or sub-network). It is not talking about a specific node.

---
Tags: graphs
---


# Question
Title: What is the expected number of nodes at depth d of a tree after i random insertions
Suppose one wanted to build a tree at random. Let the first insertion at step $i = 1$ be the root node. From here, nodes are inserted into the tree at random one at a time. How would one go about calculating the expected number of nodes $E(d)$ at depth $d$ after $i$ insertions?

For example, At $i = 1$, it's just the root node, so $E(0) = 1$ and all other depths will have zero nodes. At $i = 2$, $E(0) = 1$ and $E(1) = 1$ as the inserted node has to be at depth 1 from the root. At $i = 3$, the next node may either be attached to the root node or the existing node at depth one, so the tree may either look like:

`*
 / \
 * *`

Or:

`*
 /
 *
 /
 *`

Depending on what happend at $i = 3$, at $i = 4$ there's either a $2/3$ chance of the new node attaching at depth 2 and $1/3$ attaching at depth 1, or an even $1/3$ probability of the new node attaching at the root, the node at depth 1 or the node at depth 2. Keeping random insertion in mind (not a binary or balanced tree in any way), how would one go about calculating the expected number of nodes at depth $d$ after $i$ insertions?

# Answer
Let $X\_{d,t}$ denote the expected number of nodes at level $d$ and time $t$, and let $p\_{d,t}$ be the probability that at time $t$, a node is added at level $d$. Our indexing is such that $p\_{0,0} = X\_{0,t} = 1$. Clearly $$ X\_{d,t} = \sum\_{s=0}^t p\_{d,t}. $$ Suppose that at time $t-1$, the number of leaves at depth $d-1$ is $X$. Then the probability that at time $t$ a leaf is added at depth $d$ is $X/t$. The expectation of this across the first $t-1$ steps is exactly $X\_{d-1,t-1}$, and so $$ p\_{d,t} = \frac{X\_{d-1,t-1}}{t}. $$ Therefore $$ X\_{d,t} = \sum\_{s=1}^t \frac{X\_{d-1,s-1}}{s}. $$ What does this look like? Let's use generating functions: $$ P\_d(z) = \sum\_{t=0}^\infty X\_{d,t} z^t = \sum\_{t=0}^\infty \sum\_{s=1}^t \frac{X\_{d-1,s-1}}{s} z^t = \sum\_{s=1}^\infty \frac{X\_{d-1,s-1}}{s} \sum\_{t=s}^\infty z^t = \sum\_{s=1}^\infty \frac{X\_{d-1,s-1}}{s} \frac{z^s}{1-z}. $$ Notice that $$ \int\_0^z P\_{d-1}(w) dw = \sum\_{s=1}^\infty X\_{d-1,s-1} \int\_0^z w^{s-1} dw = \sum\_{s=1}^\infty X\_{d-1,s-1} \frac{w^s}{s}. $$ Therefore $$ P\_d(z) = \frac{1}{1-z} \int\_0^z P\_{d-1}(w) dw, \quad P\_0(z) = \frac{1}{1-z}. $$ We can calculate $$ \begin{align\*} P\_0(z) &= \frac{1}{1-z} \\ P\_1(z) &= \frac{-\log (1-z)}{1-z} \\ P\_2(z) &= \frac{1}{2} \frac{\log^2(1-z)}{1-z} \\ P\_3(z) &= \frac{1}{6} \frac{-\log^3(1-z)}{1-z} \end{align\*} $$ A pattern becomes apparent, and is easy to prove by induction: $$ P\_d(z) = \frac{1}{d!} \frac{\log^d (1-z)^{-1}}{1-z}. $$ We can pack all this data into a bivariate generating function: $$ P(z,w) = \sum\_{d \geq 0} X\_{d,t} z^t w^d = \frac{\exp (w\log (1-z)^{-1})}{1-z} = (1-z)^{-w-1}.$$ In principle, we can compute $X\_{d,t}$ asymptotically from the generating functions; but it is easier to do this directly: $$ \begin{align\*} X\_{0,t} &= 1 \\ X\_{1,t} &= \sum\_{s=1}^t \frac{1}{s} = \log t + O(1) \\ X\_{2,t} &= \sum\_{s=1}^t \frac{\log s + O(1)}{s} = \int\_1^t \frac{\log s + O(1)}{s} ds + O\left(\frac{\log t}{t}\right) = \frac{\log^2 t}{2} + O(\log t) \\ X\_{3,t} &= \sum\_{s=1}^t \frac{\log^2 s + O(\log s)}{2s} = \int\_1^t \frac{\log^2 s + O(\log s)}{2s} ds + O\left(\frac{\log^2 t}{t}\right) = \frac{\log^3 t}{6} + O(\log^2 t) \end{align\*} $$ Generalizing, we get $$X\_{d,t} = \frac{1}{d!} \log^d t + O(\log^{d-1} t).$$ With more work, it is possible to obtain lower order terms as well, indeed a polynomial in $\log t$ followed by a Laurent series.
> 9 votes

---
Tags: data-structures, trees, average-case
---


# Question
Title: Is there a shell between the kernel and hardware
First and foremost, i know what a shell, kernel is. Now the dilemma.

Today i had my systems viva in college. The examiner asked me is there a shell between the hardware and the kernel. Obviously, i said no, and the gave the usual explanation that the shell is an interpreter, it takes the user input, interprets the command and communicates with the kernel via system calls.

He then says what if i say that there is a shell between the hardware and kernel. I said it can't because there is no point. The job of the kernel itself is to interface with the hardware why will the shell be involved.

Then he started arguing that kernels are itself a set of programs, the how can they run another program. Now i got confused.

So if anyone could clear my query that whether a shell exists or not. And the biggest one, how can a kernel run a program. Is it because the kernel is in memory and its starts the init process and all other programs are run by it

# Answer
Given the details you have given us, you are of course right. There is no shell between the hardware and the kernel; that's just silly. Asking "but what if there were?" would be like asking "but what if pigs could fly?".

It is likely that either there was some misunderstanding or that the examiner is confused. The former is much, much more likely.

One thing I might critique is your characterization of a shell as an interpreter. While a shell *is* an interpreter, not every interpreter is a shell. I suppose it is possible that the examiner was asking a follow-up question to see if you understand that.

As far as how a kernel runs programs.... read a standard operating system textbook. The details are adequately covered in any standard OS textbook.

The thing is... I'm not sure why you're asking us. Why not ask your professor or examiner? We can't tell you what was in your examiner's head.
> 5 votes

# Answer
Most kernels do not talk to hardware directly unless you are talking about a monolithic kernel. Instead, with a micro-kernel architecture a system will use kernel loadable modules (device drivers). So now we can argue about the distinction between the kernel and a device driver - Does the kernel talk to hardware directly if it must go through a device driver? The reason this question is important for your question is because we have to see if we can in any way categorize the way a kernel talks to hardware as using a shell.

Shell requirement 1 - A text based interface that translates a string or series of strings into some action. I'm not sure this is even a requirement of a shell. A Unix CLI translates text but a shell doesn't have to be a CLI. However lets consider it a requirement anyway. Device drivers most definitely can do this. The category of device drivers known as char or character devices receive text and interpret it. How you would implement the `device_write` method in a char-based device driver - http://www.tldp.org/LDP/lkmpg/2.4/html/x579.html

If being a text interpreter is the only requirement then yep, there is a shell between the OS and hardware.

Shell requirement 2 - A different address space or process. It could be argued that even in a micro-kernel that the char device drivers become a part of the kernel when loaded. If a shell is a layer that forms a separation or boundary between components then a same address space device driver really only has a boundary that is defined by a method call which isn't much of a boundary at all. Can you have a device driver that interprets text AND is in a different address space than the kernel? Most definitely - while not the norm yet if you look into microdrivers or user-space device drivers you'll find that they do exist.

Shell requirement 3 - Purpose. If a "shell" is just a layer around something that is communicated with via a sequence of text then there are shells around hardware. As the most common type of shell that users have interfaced with is a Unix CLI the description of a shell has often been corrupted to describe a Unix CLI instead of the more generic idea of a shell. So if a shell is just a layer around something, yes you have a shell around hardware. If you want to compare it more to a Unix CLI well then my 1st and 2nd requirements above get us most of they way to being similar to a Unix CLI so whats left?

Handle user input - Your examiner asked about a kernel -\> hardware shell so I'd argue that handling user input was not in their requirements list of a shell. However would the user ever submit text to a hardware device driver? Maybe...old modems required a series of `AT` commands to correctly initialize them.

Limited actions - Another characteristic of a shell that is really a Unix CLI characteristic is the translation of user text into system calls - a Unix CLI is really about providing a way to convert text into syscalls and is the users interface to the kernel. So I'd argue that a device driver is not a shell in the Unix CLI sense because it doesn't exist to convert text into system calls (although some syscalls like sprintf might get used).

TLDR; A device driver is a shell but not a Unix CLI.
> 1 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Relation between digraph and NP-Complete problem
Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance:
Input: A digraph $G=(V,E)$ and two nodes $u,v \in V$
Question: Is there a path in $G$ from $u$ to $v$?
Can we say this problem is NP-Complete problem since the digraph have only two nodes that they have a path from one another and this makes it be a Hamiltonian Path.
Hints are appreciated!

# Answer
> 3 votes
When a problem is **NP**-complete, it doesn't necessarily mean that *all* instances are hard to solve. It just means that *enough* instances are hard to solve that, if you could solve this problem efficiently, you could do the same for all problems in **NP**. Enough, in this case, does mean infinitely many1 and that should lead you towards looking at large inputs if you want to find hard cases.2

For example, the fact that 3-SAT is **NP**-complete doesn't mean that you would have any difficulty telling me whether the formula $(X\vee Y\vee Z)$ is satisfiable. In your example, you've observed that, for a graph with a single edge, that edge is a Hamiltonian path. That doesn't mean that it's hard to tell whether a graph has a single edge, or that it's easy to compute Hamiltonian paths on all graphs.

---

1 Probably infinitely many, anyway. If **P** = **NP**, there wouldn't be any "hard" instances of **NP**-complete problems.

2 Note that, strictly speaking, there's no such thing as a single "hard case" since, if we restrict to that single input, the problem can be solved in constant time. Properly, I mean a whole infinite class of instances such that it's "hard" to write an algorithm that answers the problem on that whole class of inputs.

---
Tags: complexity-theory, graphs, np-complete, hamiltonian-path
---


# Question
Title: Does an enumerator print the first occurrence of a word in finite time?
For a proof I need to use the fact that every word in the language of an enumerator occur on the output paper in finite time. Is it true? For example, the language of the natural numbers in decimal representation. Can the enumerator print the odd numbers first and then the even numbers? (if yes, I am wrong)

$1, 3, 5, 7, ..., 2, 4, 6 ,8, ...$

As I know, we get to the even numbers but not in finite time (maybe transfinite induction based on this)

# Answer
> 5 votes
Your interpretation is correct, and the easiest way to look at it is to know both definitions of recursively enumerable sets:

1. There is an algorithm (potentially running forever) that enumerates the members of $S$.
2. There is an algorithm for which the algorithm halts only on elements of $S$.

These two definitions are equivalent, and if you use the second one then you can easily answer your own question.

However, do note an important caveat. Although for any given word $w \in S$ there is some time $T\_w$ such that after $T\_w$ steps, $w$ will have been enumerated. However, there is no way to bound $T\_w$ from above as a function of $w$. It can grow faster than any computable function.

# Answer
> 2 votes
Yes, it is true. Every word in the output of the enumerator will appear in finite time.

An enumerator cannot print the sequence $1,3,5,7,\dots,2,4,6,8,\dots$, because it'll never finish enumerating the odd numbers and never get to the even numbers. To put it another way: it cannot enumerate that sequence, because that is not even a sequence.

Formally, a sequence of integers is a function $f:\mathbb{N}\to\mathbb{Z}$ from the natural numbers to the domain of the sequence. Thus, $1,3,5,7,\dots$ is a sequence; it corresponds to the function $f(n) = 2n+1$. However, $1,3,5,7,\dots,2,4,6,8,\dots$ is not a sequence; there is no corresponding sequence. An enumerator outputs a sequence. From this definition, it is easy to see that any output of the enumerator appears on the output in finite time: if $y$ is an output of the enumerator, then there exists some $i\in \mathbb{N}$ such that $f(i)=y$, and thus $y$ appears after $i$ steps.

---
Tags: turing-machines
---


title: Left recursion for LL(1)

text:
# Question
Title: Left recursion for LL(1)
Hi I am trying to solve a LL(1) form question for first n follow rule The question is

```
A::=BC|C
B::=Bd|ef
C::=gh|j

```

What I have done to eliminate left recursion

```
A::=CA’
A’::=CB’
A’::=ϵ
B::=efB’
B::=dB’
B’::=ϵ
C::=gh
C::= j

```

Is it correct?

Thanks guys, it has been solved.

# Answer
The only left-recursive rule is the one for $B$. The nonterminal $A$ produces no problems, $\operatorname{first}(B) = \\{ e \\}$ while $\operatorname{first}(C) = \\{ g, j \\}$. So you need to eliminate left recursion for $B$:

\begin{align} B &::= e f B' \\ B' &::= d B' \mid \epsilon \end{align}
> 0 votes

---
Tags: formal-languages, parsing, left-recursion
---