# Question
Title: Feasibility of linear inequalities with binary variables
I have a system of linear inequalities of the form $A^t x \leq b$, where each of the $x\_i$'s is a binary variable in $\\{0, 1\\}$. Are there any known fast and practical algorithms that can find a feasible solution or prove that the system has no solutions?

I need this to generate an initial solution to the heterogenuous fleet VRP where the number of unknowns is ~ 10s of millions in each instance.

# Answer
Use an off-the-shelf integer linear programming solver. That's exactly what they are designed to do. The problem is NP-hard in general, so there are no guarantees -- there are certainly some problems that no existing solver can solve in any reasonable amount of time -- but you might get lucky.

Checking whether a feasible solution exists is also NP-complete, and it is (asymptotically, in general) about as hard as finding a feasible solution if one exists.
> 2 votes

---
Tags: algorithms, reference-request, decision-problem, integer-programming
---


# Question
Title: Lazily computing a random permutation of the positive integers
Are there any existing efficient algorithms for lazily computing a random permutation of the positive integers in a given range (e.g. the range offered by an unsigned integer type in a CPU)?

What I mean is this:

An algorithm that, given a source of randomness and a positive integer range (for simplicity it could be restricted to starting at 0 and ending at n), can be asked to produce the next value in that range. This can be repeated n times, and a different number is provided by the algorithm each time.

If the caller were to push all of the values retrieved from the algorithm into a queue the resulting ordering would be just as random as if the result had been generated with the Fisher–Yates shuffle.

The naïve implementation would be to pick a random number in the range, check to see if it has already been selected, and choose again if so. This algorithm starts efficient enough, but has increasing complexity for subsequent calls -- too expensive for real-world applications. To really be useful it would have to be O(1) for each trial, though a good logarithmic time might be applicable.

It has to be lazy because with large ranges (such as a 64 bit unsigned integer) it would take Exabytes of storage to precompute the whole permutation, and it is unlikely that a real-world application is going to actually need all of the range; merely it needs that the entire range was considered in values it is actually going to use.

Essentially the problem is just lazily generating a mapping between the integers in a range and a random permutation of those same integers, though being able to access the mapping at arbitrary points instead of just sequentially is but a bonus.

# Answer
Yes. Use a block cipher with a small block size. This is extremely efficient and requires extremely little state.

A block cipher is a map $E : K \times X \to X$ such that, for every $k \in K$, $E(k,\cdot)$ is a permutation on $X$ (a bijective function $X\to X$). Moreover, if $k$ is chosen uniformly at random, then $E(k,\cdot)$ acts in a way that is computationally indistinguishable from a function chosen uniformly at random from all permutations on $X$.

Thus, a simple solution is to let $X$ be the set of possible values of an unsigned integer, e.g., $X=\\{0,1,2,\dots,2^{64}-1\\}$, let $x$ denote a counter ($x \in X$) and $k$ a random key. The state of your pseudorandom generator is $x$ and $k$. When you want a new random number, you output $E(k,x)$ and then increment $x$. This requires very little memory, is extremely efficient, and is provably good (if the block cipher is secure, which is a reasonable assumption given the state of modern cryptography).

You can find information on how to build a block cipher with a small block size here:
> 6 votes

# Answer
Place your numbers as the leaves of a balanced binary tree, and assign each non-leaf node a number representing how many leaves are below it.

To choose a new number, randomly descend the tree, at each step moving left or right proportional to the leaf counts of the left and right child nodes. Then when you finally get to a leaf, that is the next number in the permutation and cannot be used again. Cross it off, and propagate a $-1$ to the leaf counts back up the tree.

For example, with 8 numbers you would have:

For the first number, you randomly descend the tree going each way with left/right probability 50% at each node until you reach the a leaf (say, you got the leaf representing the number 4)

The first part of your permutation is this leaf's number: $$p = (4,\dots)$$

Now you remove the leaf you got from the tree, and propagate the new leaf counts back up the tree.

Now you have the new tree,

which you can descend, except with modified probabilities at each node (say you end up with the second number being 8):

The beginning of your permutation is now, $$p = (4,8,\dots)$$

Then delete the leaf you got, and propagate the leaf count correction back up the tree.

You can just repeat this process until you have as many numbers in the permutation as you need.

The initial values in the tree are all known based on the tree height, so you can lazily build the tree as you go rather than constructing it beforehand.
> 2 votes

---
Tags: online-algorithms, random-number-generator
---


# Question
Title: Does every NP problem have a poly-sized ILP formulation?
Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem in NP.

But I've seen papers on specific NP problems where people write things like "this is the first poly-sized formulation" or "there is no known poly-sized formulation". That's why I'm puzzled.

# Answer
This answer is mostly a recap of the comments on the question above.

If a problem is NP-complete, it can indeed be reduced to ILP, by using Karp's reductions (― Joe, andy). Claims of "polynomial sized formulations" from one problem to another, are likely meant as more direct formulations, as opposed to multiple reductions through SAT (― Kaveh).
> 5 votes

# Answer
Yes. Every NP problem has a polynomial-sized ILP formulation.

Here is why. Every NP problem has a polynomial-sized formulation as an instance of SAT. Moreover, all of the usual boolean operators -- logical OR, logical AND, logical NOT, etc. -- can be expressed in ILP, using a constant number of variables and inequalities per boolean operator. See Express boolean logic operations in zero-one integer linear programming (ILP) for details of how to do that. Thus, we get at most a constant-sized blow-up when going from SAT to ILP. This implies that there is a polynomial-sized formulation of every NP problem as an ILP problem.
> 2 votes

---
Tags: complexity-theory, np-complete, reductions, linear-programming
---


# Question
Title: How to explain the steps in the implementation of hashing functions like SHA1
I was reading the article about the SHA1 hashing function (I know it is not secure anymore) and I've found a pseudocode implementation on Wikipedia.

I can see that there are a lot of mathematical operations, and what I wanted to know is the justification of each step in this hashing function. I want to know, for example, how each part increases the security of the function. How do we know that these operations are gonna produce a drastic change in the output when a minimum change is made in the input?

Is there a book about the theory behind hashing function? Maybe a book that explains mathematical functions or operations that maps the input to a very large output space such that is very hard to do the inverse way.

Is there a very simple hashing function that can be studied and that are examples of attacks? Is there some paper that explains the evolution of these functions and the justification for some math operations in this?

# Answer
I recommend you spend some time with some crypto textbooks, in particular the Handbook of Applied Cryptography and Antoine Joux's Algorithmic Cryptanalysis. They explain some of the details of hash functions. You might also try reading some of the questions on Crypto.SE; there's a lot written there.

In addition, do some self-study about unbalanced Feistel networks. They are part of the core of SHA1. You can find information about them on Wikipedia and in the cryptographic literature.

You might also like to read the submissions to the SHA3 competition. Every one came with a detailed technical document that explains the design criteria and security analysis of the hash function.
> 2 votes

---
Tags: algorithms, cryptography, hash
---


# Question
Title: How does the processor find kernel code after an interrupt?
When an interrupt occurs, the processor preempts the current process and calls kernel code to handle the interrupt. How does the processor know where to enter the kernel?

I understand that there are interrupt handlers which can be installed for each interrupt line. But since the processor only executes 'hardwired logic', there has to exist some predefined place that points to either an interrupt handler itself, or some code that executes before the handler (since there can be multiple handlers for one interrupt line, I assume the latter).

# Answer
On startup, the kernel will initialize an interrupt vector table (called an interrupt descriptor table or IDT on x86) that points to an interrupt handler for each line.

Before the 80286, the IDT was always stored at a fixed address; starting with the 80286, the IDT is loaded using the `LIDT` instruction.

Interrupt vector tables point to a single handler per interrupt line; that being said, a kernel could choose to, for example, provide an interrupt handler that runs several other interrupt routines, or provide a single handler that covers some or all interrupts. Linux does these things by providing a generic interrupt handler that determines which interrupt line was called and finds the appropriate downstream handler to call.
> 13 votes

# Answer
Yes, there is a predefined place that contains the address of code to jump to: an **interrupt vector**. Depending on the processor, this can be a specific location in physical memory (8088), a specific location in virtual memory, a processor register, a location in memory indicated by a register (ARM, 386), …

The details vary on different processors, but the main common elements to handling an interrupt in the processor are:

* Mask interrupts (so that any subsequent interrupt will have to wait).
* Set the processor mode to kernel or interrupt mode (if the processor has such modes).
* Save the value of the program counter to a known place (register or memory).
* Possibly save the value of other registers, or switch between register banks).
* Execute the next instruction (at the new PC value).
> 13 votes

# Answer
The other two answers (at the time of writing) talk about interrupts and the IDT. This is correct, however, on a modern Intel-esque CPU, there are no fewer than three ways to call into a kernel.

**Method #1: Interrupts.**

This is explained above. You set up an entry in the interrupt descriptor table/interrupt vector, and then execute a software interrupt to enter the kernel.

The main advantage of this method is that a typical kernel needs to be able to handle interrupts anyway, and it works on archaic hardware.

**Method #2: Call gates.**

A call gate is a special kind of segment selector. The target of the call needs to be loaded in the global or local segment descriptor table (GDT and LDT respectively). If you then perform a far call instruction using the call gate as the segment (the offset of the call is ignored), this allows you to call more privileged code. Call gates are extremely flexible; the IA-32 architecture has four privilege levels, and call gates let you call any level.

I don't believe that Linux ever used call gates, but Windows 95 did. Win95 kernel services (`krnl386.exe` and `kernel.dll`) actually ran in user mode (ring 3). The highest privilege level (ring 0) was only used for drivers and a microkernel which performed only process switching. Calling into drivers was done using call gates. This allowed legacy 16-bit code (of which there was a lot!) to use Win95 drivers just using a standard far call, just like they always did.

Inadequate protection of the global descriptor table was the cause of several Windows 95 exploits, which managed to install their own call gates by writing over memory.

**Method #3: SYSCALL/SYSRET and SYSENTER/SYSEXIT**

These are two sets of instructions, independently invented by AMD and Intel, but they essentially do the same thing. SYSCALL/SYSRET came first and was AMD-only, SYSENTER/SYSEXIT was Intel, but AMD implements it now. So I'm going to describe SYSENTER/SYSEXIT.

Unlike call gates, SYSENTER can only be used to transfer to ring 0, and can only transfer to one location. However, it has the advantage of being extremely low-latency because unlike a call or interrupt it doesn't touch the stack.

The transfer location is set up using three model-specific registers: one for the segment information, and one each for the instruction pointer and stack pointer of the kernel code. Because nothing is "pushed" onto the stack, the user mode code is responsible for telling the kernel where to return to by passing the return instruction pointer and stack pointer in registers. The kernel is responsible for restoring the stack pointer, and the SYSEXIT instruction restores the instruction pointer.

Further information on the SYSENTER and SYSEXIT instructions.
> 1 votes

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


# Question
Title: Show that the regular languages are closed against taking "the second half"
Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the creation of such NFA proving it is regular.

However, what if you wanted to prove the 2nd half string is regular, not the 1st half of a string. That is,

$$\mathrm{2HALF}(L) = \\{ x\mid yx\in L \text{ for some }y\text{ with } |y|=|x|\\}\\,.$$

Compare this to the standard

$$\mathrm{HALF}(L) = \\{ x\mid xy\in L \text{ for some }y\text{ with } |y|=|x|\\}\\,.$$

I struggled on a solution, trying to use the same method as used on $\mathrm{HALF}(L)$ but can't seem to wrap my head around it.

# Answer
Hint: if $L$ is regular, the reversal $L^R$ of the language $L$ is regular; see How to show that a "reversed" regular language is regular. You should be able to use this fact.

Alternative hint: guess the middle point (non-deterministically), then...

Since this is an exercise problem, I am giving only a hint, not a full solution. Try solving it yourself.
> 2 votes

---
Tags: formal-languages, regular-languages, finite-automata, closure-properties
---


# Question
Title: How to write regular expression excluding certain pattern aba from albhabet set {a,b}?
Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite?
Is there any generic way to write a regular expression for the set of all words that do not contain a certain pattern?

# Answer
> 4 votes
Maybe the easiest (though not necessarily fastest, if done by hand) way to do this is to make use of the many equivalent formalisms for regular languages:

1. Create an NFA that accepts all words that contain the pattern. (This NFA will consist of a chain of transitions that are labeled with the pattern and additionally can loop in the initial or final state on every symbol.)
2. Transform that NFA into a (complete) DFA using a standard algorithm.
3. Make all the accepting states of the DFA non-accepting and vice versa.
4. Translate the inverted DFA into a RE using a standard algorithm.

# Answer
> 0 votes
It's not clear from the question whether you want to know if such a regexp exists, or to find a small regexp.

If you just want to know whether such a regexp exists, the answer is yes; it follows from closure properties for regexps, such as that the complement of a regular language is regular.

If you want to find a minimal regexp, or a small regexp, see Is regex golf NP-Complete? or Smallest DFA that accepts given strings and rejects other given strings.

---
Tags: algorithms, regular-expressions
---


title: RMQ with $O(\sqrt{n})$ space?

text:
# Question
Title: RMQ with $O(\sqrt{n})$ space?
I'm asked to design an RMQ data structure (Range Minimum Query: return index of $min$ in a range $\[i,j\]$) for an array that has $\<=\log(n)$ local minimums (a local minimum is an index $i$ such that $A\[i-1\]\>A\[i\]\<A\[i+1\]$).

There are 2 restrictions:

* Only $O(\sqrt{n})$ additional space (rather than $O(n)$ which is used for the regular RMQ d.s. Also see here)
* Only a constant number of entry readings from the original array while answering a query

I thought of a solution that uses $\log(n)\log\log(n)$ space. Which is $\< \sqrt{n}$ for $n\>1165$ according to wolframalpha. (as @jbapple said, $\log(n)\log\log(n)=O(\sqrt{n})$ so that's fine)

**edit: i found an error in the solution: in part 3, each item needs to know which section it belongs to (or at least the closest local min to it) - that's already $O(n)$ additional space.**

***However, i won't delete it so maybe it can be modified to a correct solution***

**My solution:**

Find all local minimums and save pointers to them in $O(n)$ time, $O(\log n)$ space $(\<\sqrt{n}\space)$ .

Apply regular RMQ on $\log(n)$ local minimums (powers of $2$ technique - section 3.3 page 5 in this paper). This takes $n\log(n)$ space, but $n$ in my case is $\log(n)$ (number of "representatives"), so it'll cost $\log(n)\log\log(n)$ space only. *This is for part 3 - see ahead.*

Answering a query:

There are 3 types of queries:

1. Range begins just after a local minimum and ends just after the next one: This is easily solved in $O(1)$ since it's either the leftmost or rightmost entry
2. Range between 2 local mins (not including): Also easy (same method)
3. Overlapping range: This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

* Sections of "local min to local min" can be solved in $O(1)$ using the regular RMQ we built above.
    * Regarding the other 2 sections, for each of them we can determine the min in $O(1)$ (must be either leftmost or rightmost item).
    * Finally we're left with exactly 3 numbers. Get their min in $O(1)$

# Answer
> 2 votes
Here's how it works:

I'll provide 2 solutions:

1. $O(\log{n})$ space and $O(\log{\log{n}})$ query.
2. $O(\log{n})$ space and $O(\log{\log{\log{n}}})$ query.

**1) Using binary search on local mins.**

Find all local minimums and store them in an array $B$ in their original order - $O(n)$ time, $O(\log{n})$ space ($\<O(\sqrt{n})$). Also, let each item remember its original index. Now apply regular $RMQ\<O(n),O(1)\>$ structure on $\log{n}$ local minimums ($\log{n}$ space.) To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $\[i,j\]$, we binary-search the array $B$ for indices $i$ and $j$ to find the closest index which has a local\_min.

Answering a query:

There are 3 types of queries:

1. Range begins just after a local minimum and ends just after the next one:

First, we need to recognize we’re in this case. Perform a binary search on array $B$ for index $j$ or the smallest index larger than $j$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{n}})$.

2. Range between 2 local mins (not including):

Same method as above, but this time we’ll find $i-2$ and $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(loglogn)$.

3. Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture). Again, to recognize the case, binary-search for $i,j$ in $B$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and i overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A\[i\]$ or $A\[j\]$). Solve query $\[i,j-1\]$ by RMQ, compare the returned min with $A\[i\]$ and $A\[j\]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{n}})$.

**2) Using y-fast trie on local mins.**

Find all local minimums and store them in a y-fast trie structure (call it $Y$) and let the keys be the original indices - $O(n)$ time, $O(\log{n})$ space. Now apply regular $RMQ\<O(n),O(1)\>$ structure on $\log{n}$ local minimums ($\log{n}$ space.) To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $\[i,j\]$, we search $Y$ for indices $i$ and $j$ (or their pred and succ) to find the closest index which has a local\_min. Search of pred/succ in a y-fast-trie of $n$ elements takes $O(\log{\log{n}})$.

Answering a query:

There are 3 types of queries:

1. Range begins just after a local minimum and ends just after the next one:

First, we need to recognize we’re in this case. Search for index $j$ or its successor in $Y$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{\log{n}}})$.

2. Range between 2 local mins (not including):

Same method as above, but this time we’ll find $i-2$ and $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(\log{\log{\log{n}}})$.

3. Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

Again, to recognize the case, search for $i,j$ in $Y$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and $i$ overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A\[i\]$ or $A\[j\]$). Solve query $\[i,j-1\]$ by RMQ , compare the returned min with $A\[i\]$ and $A\[j\]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{\log{n}}})$.

**Proof for cases 1&2:**

Theorem: in this type of ranges, the min is either the leftmost or rightmost entry. Proof by contradiction: Suppose the min is somewhere inside the block, and not at the edges. If it’s the min then it’s smaller than both its left and right neighbors. Thus it’s a local\_min by definition. This is a contradiction because we assumed we have a block from a local\_min to the next local\_min (no local\_mins’s in between).

---
Tags: algorithms, data-structures, efficiency
---


# Question
Title: How are lamport clocks implemented in real world distributed systems?
Can anyone explain, how lamport clocks implementations are used in modern distributed systems? Can you name an open source package which implements this algorithm?

# Answer
> 4 votes
Amazon's Dynamo \[1\] is a distributed storage system that uses vector clocks "to capture causality between different versions of the same object". Section 4.4 of the paper describes how exactly Lamport clocks are used to manage data versioning.

Some of the open source implementations of Dynamo are Riak \[2\] and Voldemort \[3\].

\[1\] G. DeCandia et al.: Dynamo: amazon's highly available key-value store. SOSP 2007:205-220

\[2\] http://basho.com/riak

\[3\] http://www.project-voldemort.com

---
Tags: distributed-systems, synchronization
---


# Question
Title: Can the lambda functions in Church numbers be swapped?
I've learned that one can represent natural numbers with lambda calculus like this:

\begin{align\*} c\_0 &= \lambda s. \lambda z. z\\ c\_1 &= \lambda s. \lambda z. s~z\\ c\_2 &= \lambda s. \lambda z. s~(s~z)\\ c\_3 &= \lambda s. \lambda z. s~(s~(s~z))\\ \end{align\*}

But could one also write

\begin{align\*} c'\_0 &= \lambda z. \lambda s. z\\ c'\_1 &= \lambda z. \lambda s. s~z\\ c'\_2 &= \lambda z. \lambda s. s~(s~z)\\ c'\_3 &= \lambda z. \lambda s. s~(s~(s~z))\\ \end{align\*}

?

Why / why not?

# Answer
Sure, except it's going to be more painful to use the numbers with the swapped arguments because in many cases you want to apply a Church numeral only to the argument $s$ and leave $z$ specified. Thus, instead of writing $c\_n \\, e$ you will have to write $\lambda z . c'\_n \\, z \\, e$ whenever that happens.
> 1 votes

---
Tags: lambda-calculus, church-numerals
---


# Question
Title: Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy
I'm looking for a complete proof of $\mathrm{PH=SO}$. The (admittedly few) textbooks and papers i've looked at all either state that it's a corollary from Fagin's Theorem, or leave it as an exercise to the reader. Even Stockmeyer's original paper on the hierarchy (this one, right?) proves the result in a "Remark." section, so it's not exactly the most detailed proof.

Just so we're clear, i did write my own version of the proof; it's exactly because of all the work i had to do in order to prove said result, contrasted with the one-paragraph proofs commonly found in the literature, that makes me curious about what kind of insight i might be missing.

As for how my proof proceeds, i can give an high-level overview of the harder direction. Using the certificate version of the hierarchy, and second-order logic with alternating quantifier blocks, the proof goes by induction. Base case is Fagin's Theorem. For the inductive step, you have a second-order formula deciding the input+certificate relation, so all you need to do is to introduce some existential quantifiers over the given formula quantifying all of its relational symbols, plus a formula that states that the interpretation given by the quantifiers does contain the input.

Of course, like any high-level overview, this is easier said than done. At least in my proof, there's a fair amount of translating in order to make things work. Plus there's the fact that the usual certificate definition is over languages, and we're dealing with arbitrary finite structures, so there's some conversion there too. Then you have to prove that all the stuff you did is in fact correct. All in all, it's not pretty.

So i have to ask: Is there any proof of this result that isn't afraid of working out some of the details, but has the same intuitive clarity as the usual short proof?

# Answer
It's one of those proofs that's essentially obvious once you can prove Fagin's theorem that the existential fragment of **SO** is exactly **NP**. Alternating quantifiers in the **SO** formula takes you up the polynomial hierarchy more or less by definition.

Proposition 7.35 of Libkin's *Elements of Finite Model Theory* proves that **MSO** expresses complete problems at every level of **PH**. Corollary 9.9 of the same book is that **SO**=**PH**; but the proof consists of a sketch with an exercise to fill in one of the steps. The proof that **SO**=**PH** is also essentially Exercise 7.5.18 of Ebbinghaus and Flum's *Finite Model Theory* (2nd ed.). Immerman's *Descriptive Complexity* states the equivalence as Theorem 7.21 and Corollary 7.22 but leaves the proof as an exercise and credits the result to Stockmeyer's paper.

Given all of that, I doubt you'll find a proof in print. The details probably are fiddly but your outline sounds correct.
> 1 votes

---
Tags: reference-request, descriptive-complexity
---


# Question
Title: Can languages with infinite strings be recursively enumerable?
I am not 100% sure about the definition of **recursively enumarable** languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but it does not have to halt on different inputs.

But suppose I have a language consisting of uncountable size with words of infinite length. Will Turing machine halt with a word of infinite length?

Consider a language constisting of all binary strings (I can produce such a set by diagonalization - Cantors rule, for example). Is this language recursively enumarable? If so, can you tell me why? I have not found any definition of this that would explain the behavior of TM with such inputs...

# Answer
> 2 votes
I agree with FrankW's answer regarding semi-decidability, though his answer is based mostly on an example. But I am not sure he answers your question, or that he answers with sufficient precision.

The problem is that your question is ambiguous. You use, and even *emphasize in boldface*, the expression **recursively enumerable**, but you give the definition that seems more intended for **semi-decidability**. I realize that it is weell known and easy to show that these two concepts are equivalent when considering languages that are sets of finite strings, and we do not usually distinguish them.

However these concepts were originally defined only for finite strings, or natural numbers, which amount more or less to the same. Basic computability theory assumes finiteness (the use of Gödel numbers requires finiteness of description, for example). I know there is work on automata for infinite strings, though I am not familiar with it.

If you consider languages with infinite words, concepts such as **recursively enumerable** or **semi-decidable** are no longer equivalent. The former means that there is a Turing Machine (TM) that can enumerate all the words of the language. The latter (also called **recognizable**) means that there is a TM that will halt in an accepting state when given a word of the language, and will reject or loop otherwise.

The concepts can extend to languages with infinite strings. However, as shown by FrankW's answer, a semi-decision procedure requires that words in the language be recongnizable by considering only a finite prefix. In other words, such a language $L$ with infinite words is semi-decidable iff it is of the form $L=M\cup N\Sigma^\infty$ where $\Sigma$ is the alphabet, $\Sigma^\infty$ is the set of infinite strings over $\Sigma$, and both $M$ and $N$ are semi-decidable sets of finite strings. The set of all **infinite binary strings** conforms this definition. As remarked by Shaull's comment, it is recognized by any TM that simply accepts without looking at the string. There are some subtler details about being sure of the alphabet, but that is minor.

You also have to define precisely what it means to enumerate an infinite set of infinite strings, but that can be done.

In the finite case, a recursively enumerable language is semi-decidable. The semi-decision procedure is simple, given a word $w$, you enumerate the words in the language and compare them to $w$. If there is equality, the word $w$ is accepted, else you keep enumerating.

In the case of infinite words this no longer works, very simply because checking equality of two infinite words takes infinite time. Of course, any infinite word that we may want to consider has to be computable. Hence it can be finitely represented by a TM, or a Gödel number. But this is no help. I think the TM enumerating the infinite strings in the language can be transformed into a TM that enumerate finite descriptions (Gödel numbers) of TM that just produce each one of these strings. Similarly, the infinite word $w$ that we try ro recognize can be finitely represented by a description of a TM that produces it. So now everything is finite, and we should be OK, except for the fact that checking whether two TM produce the same (finite or infinite) string is undecidable.

Basically, the problem is that infinity makes you lose the equality test, so that **recursive enumerability no longer implies semi-decidability**. However, semi-decidability still implies recursive enumerability, pretty much as in the finite case, but I would not care to give here a detailed construction for it.

While the structure of semi-decidable languages of infinite strings is limited to $L=M\cup N\Sigma^\infty$, as shown above, recursively enumerable languages of infinite strings can be much richer and complex.

# Answer
> 2 votes
As you state, the standard definition of TM acceptance requires that the TM halts after finite time.

It is still possible for a TM to accept languages that contain infinite words, *if* they can accept without reading the entire word. For example the language of all (finite and infinite) words that contain at least one $0$ is semi-decidable, since if there is a $0$, the TM will encounter it after a finite amount of time and can then accept the word.
The complement of this language however is not semi-decidable, since it is not possible to read an infinite input in finite time (and it is not possible, in the general case, to know that there is no $0$, without reading the whole input).

---
Tags: formal-languages, computability, turing-machines, semi-decidability
---


# Question
Title: What do we know about covering the edges of a graph by disjoint paths?
Two related things I have heard/know of are,

(1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?)

(2) That its NP-complete to decide if $k$ vertex disjoint paths can cover all the vertices of a graph.

* Are there edge analogues of these results?
* Does using the dual graph translate these results into their edge versions?
* If the line graph is a edge-to-vertex-dual then is there a vertex-to-edge-dual? (which will may be convert the question of finding a vertex cover by k vertex disjoint paths into a question of finding an edge cover by $k$ edge disjoint paths?)

# Answer
> 2 votes
You can cover the edges of a graph by cycles iff the graph is Eulerian (or has multiple Eulerian components). Notice that two cycles that share a vertex can always be combined into one cycle.

---
Tags: complexity-theory, graphs
---


title: Use count() in relational algebra

text:
# Question
Title: Use count() in relational algebra
> Person(name, phone)
> Mike 456-789
> Mike 123-456
> John 230-785
> $\dots \dots$

How to get those people who have more than one phone numbers with relational algebra? This sounds simple, but I am frustrated with all materials that I've learned.

Is it correct syntax to use count() like $\pi\_{name}(\sigma\_{count(phone)\>2}(Person))$ ?

# Answer
> 9 votes
A syntax of **aggregate operation** in relational-algebra (according to \[1\]) is as follows :

> $G\_1,G\_2,...,G\_n \hspace{2 mm}\textbf{g}\hspace{2 mm} F\_1(A\_1),F\_2(A\_2),...,F\_m(A\_m)(E)$
>
> where $E$ is any relational-algebra expression; $G\_1,G\_2,...,G\_n$ constitute a list of attributes on which to group; each $F\_i$ is an aggregate function; and each $A\_i$ is an attribute name.

Thus your query would look like : $\pi\_{name}(\sigma\_{phone\>1}(name\hspace{2 mm}\textbf{g}\hspace{2 mm} count (phone)( Person)\hspace{2 mm}))$

\[1\] A. Silberschatz, H. Korth, S. Sudarshan, Database System Concepts, 5th Edition

---
Tags: database-theory, relational-algebra
---


title: time complexity

text:
# Question
Title: time complexity
$$ T(n)=\sqrt{n}T(\sqrt{n})+n $$

$$T(1)=T(2)=1$$

the answer is given as $$ \Theta(n\log \log n) $$ I tried to draw recursion tree, it got all crazy

I tried using substitution method instead $$\sqrt{n}=2^{m}$$ $$T(2^{m})=2^{m/2}T(2^{m})+2^{m}$$ $$S(m)=\frac{m}{2}S(m)+m$$ $$\frac{S(m)}{m}=\frac{1}{2}S(m)+1$$ am I right?

# Answer
In the second line of your solution, you shouldn't have two terms $T(2^m)$. Here's a correct derivation: $$\begin{align} T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by $n$ we get}\\ \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting $n = 2^m$ we have}\\ \frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1 \end{align}$$ Now let $$\begin{align} S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\ S(m) &= S(m/2)+1 \end{align}$$ which is a well-known recurrence with solution $$ S(m)=\Theta(\lg m) $$ Returning to $T()$ we then have, with $n=2^m$ (and $m=\lg n$), $$ \frac{T(n)}{n} = \Theta(\lg\\,\lg n) $$ So $T(n) =\Theta(n\\,\lg\\,\lg n)$.

This has been asked before: Solving a recurrence relation with √n as parameter, though this particular substitution solution wasn't included among the answers
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language
I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\\{w\mid\\#\_{a}(w)=\\#\_{b}(w)\\}$ and non-regular (simple proof using pumping lemma) implies that the language $L$ can therefore not be regular! The proof sounds alright initially but it got messy as I thought more on it! I read in the books that the subset property of a regular language is not closed under regular languages. So, how can the proof be correct because for all I know L is a regular language that a non-regular language $a^{n}b^{n}$ as its subset. How does it say anything more?

I do know ofcourse that $L$ here is not regular and can draw production rules for it(CFG)! But, I need to clear this confusion I have above! Some help me here.

# Answer
> 5 votes
Here is what your teacher meant. Let $M=\\{a^nb^n:n\geq0\\} $. We know $M$ is not regular. Since the intersection of regular languages is regular, if $L$ were regular then so would $L\cap a^\*b^\*=M$ be, reaching a contradiction. This shows that $L$ cannot be regular.

# Answer
> 4 votes
You are correct: the fact that $L$ is a subset of a non-regular language does not prove that $L$ is non-regular. The trivial counterexample to that claim is the empty language, which is regular and is a subset of any language. (Similarly, proving that $L$ is a subset of a regular language also doesn't prove that $L$ is regular, since every language is a subset of the regular language $\Sigma^\*\\!$.)

Actually, I don't really understand why anyone would try to prove it that way. The direct pumping-lemma proof that $\\{a^nb^n\mid n\geq 0\\}$ isn't regular is hardly any more difficult than proving that $\\{w\mid \\#\_a(w)=\\#\_b(w)\\}$ isn't regular. Note also that demonstrating that a language is context-free doesn't prove that it's non-regular, since every regular language is context-free.

It occurs to me that you may have misunderstood your teacher's proof. Since the string $a^kb^k$ is in both langauges, you can prove that both langauges are non-regular by applying the pumping lemma to that string.

# Answer
> 1 votes
We often use the Pumping Lemma for regular languages as the basis of a `proof by contradiction`.

The PL says that **if** $L$ is a regular language, then **any** sufficiently long word $w$ in $L$ can be written as $w=xyz$ (with certain restrictions on $x, y, z$) and can be pumped, namely that for all $i\ge 0$, we'll have $xy^iz\in L$. Now if that doesn't hold for a particular string in $L$ (i.e., for that particular word and for some particular $i$, the word $xy^iz\notin L$), then it must have been the case that our assumption, that $L$ was regular, must have been false.

In this case, pumping the particular string $a^pb^p$, where $p$ is the integer of the PL, gives you a string with more $a$s than $b$s, which can't possibly be in $L$, so $L$ couldn't possibly have been regular. In this case, we have a non-regular subset of a non-regular language: $E=\\{a^nb^n\mid n\ge 0\\}\subseteq L$. Roughly speaking, it's the way that $E$ behaves inside $L$ that says $L$ can't be regular.

On the other hand, if we had loosened the strictures of $L$ and instead had chosen another language $L\_1=\\{a, b\\}^\*$, then we'd have $E\subseteq L\_1$ and now we'd have the non-regular $E$ as a subset of the regular $L\_1$ (because the PL wouldn't yield a contradiction, no matter what string we tried, due to the way $L\_1$ was defined).

---
Tags: formal-languages, regular-languages, closure-properties, pumping-lemma
---


# Question
Title: For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?
In general, a string $x$ is a subsequence of $w = w\_1\dots w\_n$ if there are integers $i\_1\<\dots\< i\_k$ such that $x = w\_{i\_1}\dots w\_{i\_k}$. The subsequence is proper if $k \< n$ and $k \> 0$.

With this definition given, a homework problem asks the following: Suppose $L$ and $L\_1$ are languages, and define $L \diamond L\_1$ to be the set $\\{x \in L : \text{no string } x' \in L\_1 \text{ is a proper subsequence of } x\\}$. If both $L$ and $L\_1$ are regular, does it follow that $L \diamond L\_1$ is regular? Justify your answer.

I've attempted to construct an NFA that would recognize $L \diamond L\_1$, but this went nowhere, as things soon got overly complicated. Any ideas or suggestions?

# Answer
Since this is a homework question, I'll just give a hint.

Hint: Let $L\_2$ be the set of supersequences of words in $L\_1$, i.e.,

$$L\_2 = \\{x \in \Sigma^\* : \exists y \in L\_1 . \text{$y$ is a subsequence of $x$}\\}.$$

If $L\_1$ is regular, what can you say about $L\_2$? Is it regular? If you have a NFA for $L\_1$, can you construct a NFA that would recognize $L\_2$?

If you are not sure, try some examples of regular languages $L\_1$, and work out $L\_2$ looks like for each example.
> 3 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Origins of misconception about using equality signs with Landau notation
From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other function:

$f(n) = O(g(n))$

where what we actually mean is this:

$f(n) \in O(g(n))$

What is the origin of this misconception? And why is this misconception perpetuated, even today?

# Answer
$O$ is not only used in simple statements like $f(n)=O(g(n))$. It is also used to give error terms as in $f(n) = 14\\, n\log n + O(n)$. The interpretation is still the same as @usul has described in his answer: There is a function $h \in O(n)$ so that $f(n) = 14\\, n\log n + h(n)$.

Here, writing $f(n) \in 14\\, n\log n + O(n)$ would emphasize the fact that there is a set involved in the equation, while the important point is that the leading term(s) are exactly as stated, while the $O$-term simply bounds the error. So in this context using $=$ is a sensible choice and I'd assume that it has been carried over to the case with zero leading terms in order to keep notation consistent.
> 8 votes

# Answer
As Yuval comments, "misconception" isn't the right term for the notation. It's well-defined notation, which I agree is somewhat bad and unfortunate, but it's valid. It might make sense once we say that, whenever you see a $O(\cdot)$ in a statement, you are being told that *there exists* a choice from the set $O(\cdot)$ that makes the statement true. So you can read $f(n) = O(g(n))$ as "there exists $h(n) \in O(g(n))$ such that $f(n) = h(n)$.

This may seem silly for this simple example (we could just write $f(n) \in O(g(n))$), but I think it can come in handy with more complex statements. I am thinking of proving big-O containment over a sequence of steps: \begin{align} f(n) &= ... \\ &\leq ... \\ &= O(...) \\ &= O(g(n)). \end{align} Maybe this seems nicer or prettier than trying to use $\in$ and $\subseteq$ etc. on each line.

I would guess that this, along with the fact that it's slightly quicker to write $=$ than $\in$, and easier in e.g. plain text environments, accounts for the popularity of the notation. But a historical perspective would be interesting.
> 2 votes

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


# Question
Title: kd-tree stores points in inner nodes? If yes, how to search for NN?
The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I **think** (newbie here), I am understanding the concept.

However, I was said to study Kd-trees from Computational Geometry Algorithms and Applications (De Berg, Cheong, Van Kreveld and Overmars), section 5.2, page 99. The main difference I can see is that Overmars places the splitting data in the inner nodes and the actual points of the dataset in the leaves. For example, in 2D, an inner node will hold the splitting line.

Wikipedia on the other hand, seems to store points in inner nodes and leaves (while Overmars only on leaves).

In this case, how do we perform nearest neighbour search? Moreover, why there is this difference?

# Answer
Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search:

```
Procedure NN(node), given query q
  if(node is leaf)
    Search all points, in node, update current best
  else {internal node}
    if( cut_coord(q) <= node's cut-value )
        NN(left-child)
        if( cut-coor(q) + current best distance > node's cut-value )
            NN(right-child)
        end if
    else {cut-coor(q) > node's cut value}
        NN(right-child)
        if(cut-coor(q) - current best distance <= node's cut-value)
            NN(left-child)
        end if
    end if(left/right)
  end if(node)

```

In order to perform ANN search, see the answer here.
> 6 votes

---
Tags: data-structures, computational-geometry, search-algorithms, search-trees, nearest-neighbour
---


# Question
Title: Method for measuring the 'similarity' between FSA grammars?
I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic representation of a music stream (e.g., MIDI data). The music stream has been preprocessed to divide each song into unlabeled 'segments'. An FSA is generated for each segment in each song: if I have $n$ songs, each divided into $y$ segments, I will have $n \cdot y$ separate FSAs.

I would like to compare each segment's FSA with the other FSAs in my corpus. The ultimate goal would be to do clustering within a similarity space and come up with 'classes' of segments according to how similar their construction metrics are. Thus, of particular interest are the grammars that each FSA defines (corresponding roughly certain components of the musical content in the segment). Are there techniques that might be good for comparing something like this? KL-divergence comes to mind (e.g., using it compare the distribution over strings associated with a given FSA), although there may be better/more efficient techniques?

Also, apologies if this question is either (1) trivially easy or (2) indicative of some deeper misunderstanding or (3) answered elsewhere. I'm a real nub, folks!

# Answer
> 1 votes
you might have more luck from another angle & looking into research into music piece similarity, there are researchers studying that, and while your approach can work, there are other approaches. there are large databases that look at many elements/ criteria such as lyrics, genre etc. eg Music genome project.

sometimes when theres a wide variety of algorithms a survey can help. here are two surveys on graph matching.

# Answer
> 0 votes
Since FSAs are directed graphs, your question can be generalized as "algorithm for measuring similarity between directed graphs". A google search for "graph similarity algorithm" gives pages and pages of hits, maybe one of those would be suitable for your purposes?

Once difference between FSAs and general digraphs are the edge labels, or transition symbols in FSAs, so you would have to modify these algorithms to take that into account.

---
Tags: formal-languages, reference-request, finite-automata
---


# Question
Title: Understanding the Sipser-Gacs-Lautemann theorem
The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input.

The class $\Sigma^p\_2$ contains all the languages for which there is a polinomial time Turing machine $M$ and a plynomial function $q : \mathbb{N} \rightarrow \mathbb{N}$ such that: $$ x \in L \iff \exists u \in \\{0,1\\}^{q(|x|)} \forall v \in \\{ 0,1 \\}^{q(|x|)} M(u,x,v)=1$$ Define $\Pi^p\_i=\\{\bar{L} : L \in \Sigma^p\_2 \\}$

The theorem states that the class $BPP$ is contained by the intersection of $\Sigma^p\_2$ and $\Pi^p\_2$.

To prove the theorem it is proved that for every set $S \subseteq \\{0,1\\}^m$ with $|S| \leq 2^{m-n}$ and every k vectors $u\_1, \ldots, u\_k$ $$\bigcup\_{i=1}^k(S+u\_i) \neq \\{0,1\\}^m$$ Where $S+u = \\{ x+u : x \in S \\}$ and + denotes addition modulo 2 i.e. bitwise XOR.

It is also proved that for every set $S \subseteq \\{0,1\\}^m$ with $|S| \geq (1-2^{-n})2^m$ and every k vectors $u\_1, \ldots, u\_k$ $$\bigcup\_{i=1}^k(S+u\_i) = \\{0,1\\}^m$$

I don't get why this claims imply that if a language is in $BPP$, then $$ \exists u\_1, \ldots,u\_k \in \\{ 0,1 \\}^m \forall r \in \\{ 0,1 \\}^m \bigvee\_{i=1}^k M(x,r \oplus u\_i) = 1 $$

How does the claims about sets of binary strings imply the computation above?

What I don't understand is how the translations preserve the original random strings and how can a small set of translates cover all possible random strings.

# Answer
> 3 votes
First of all, it's not clear to me that every language of the form given by your last formula is in BPP. Fortunately, we only need the reverse direction: every language in BPP can be written in this form. This will show that BPP is contained in $\Sigma\_2$. Since BPP is closed under complementation, this will complete the proof.

Start with a BPP machine with some small error probability. For appropriate $k$ (depending on the error probability), a union bound shows that the formula doesn't hold. The other direction looks more complicated, and this is probably where the other results they prove come in. Basically, you have a set of good random strings covering almost all strings, and you want to cover all of them by finitely many translates of the set. Perhaps that's what these lemmas show.

---
Tags: complexity-theory, complexity-classes, polynomial-time, probabilistic-algorithms
---


title: A relationship in a UML class diagram

text:
# Question
Title: A relationship in a UML class diagram
I am investigating a small database in a paper:

Each line is a selling record. For instance, Line 2 expresses that `Store 100 in Week 383 sold Product 653; for this selling, the move was 16 and the price was 2.19, thus the profit was 16*2.19*2=7.01` (the other columns are not very important).

The authors then show a UML class diagram as follows:

What I cannot understand (and is not explained in the paper) is the relationship between `OnSaleKey` and `DetergentKey`. Could anyone tell me what it is about in a UML diagram language?

# Answer
> 2 votes
You can have many sales of the same product in the same store and in the same week. Also, a detergent can be sold in different weeks in different stores.

This means that you have to create a class Sale, that associates an OnSaleKey to a DetergentKey.

The Sale class is an association class.

From here you can find an explanation:

> An association may be refined to have its own set of features; that is, features that do not belong to any of the connected classifiers but rather to the association itself. Such an association is called an association class. It is both an association, connecting a set of classifiers and a class, and as such could have features and might be included in other associations.
>
> An association class can be seen as an association that also has class properties, or as a class that also has association properties.
>
> An association class is shown as a class symbol attached to the association path by a dashed line. The association path and the association class symbol represent the same underlying model element, which has a single name. The association name may be placed on the path, in the class symbol, or on both, but they must be the same name.

In this case it is easier to think about the Sale class as a table in a database that associates an id from OnSaleKey to an id from DetergentKey.

---
Tags: databases, database-theory
---


# Question
Title: Don't understand closure under string reversal
I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect\_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function,

I having breaking down the syntax to english, my attempt it

for the function delta'' for a given state `q` and a symbol `t` the `r` inside the original set of states `Q` such that the state `q` exists in the modified function (in which all final states go to one final state via e-transition) ...

This is where I get confused, its sending r to the modified function delta' but I dont understand what the r stands for and how it comes to be. Furthermore I don't know what Sigma\_epsilon means, I assume its the alphabet union with {e}

I also don't see how the induction proof is trivial or easy

# Answer
> 2 votes
Both $q$ and $r$ are states in this construction. If in original $\delta'$ we can step $r\stackrel{t}{\rightarrow} q$ then in the new $\delta''$ we can step $q\stackrel{t}{\rightarrow} r$. Like stated in the proof the arrows are reversed.

You are right, $\Sigma\_\epsilon$ is $\Sigma$ plus the empty word $\epsilon$. The original automaton initially has no $\epsilon$-transitions. However it has multiple final states, and after reversing it would have multiple initial states. A possible solution is given here, using $\epsilon$-transitions, connecting a new final state from the original final ones. This is the first step, from $\delta$ to $\delta'$.

If you are still trying to decipher the construction then of course the induction is not trivial. Once you see the arrows are just reversed, then it is not hard to come up with a possible induction assumption: if I can go from $q$ via string $w$ to $r$ in $\delta'$, then I can go from $r$ via string $w^R$ to $q$ in $\delta''$. Then it is no longer difficult. It would not say "easy" as that depends on your experience with induction.

---
Tags: formal-languages, regular-languages, automata, finite-automata, closure-properties
---


title: Kleene closure of the empty set

text:
# Question
Title: Kleene closure of the empty set
In the book introduction to automata theory and languages, $L^\*$ is defined as

$$L^\* = \bigcup\_{i=0}^\infty L^i $$

The book also says that $\emptyset^\* = \\{ \epsilon \\}$. But since $\emptyset$ is the empty set

$$L^\* = L^0 \cup L^1 \cup L^2 ... $$

$$= L^0 \cup \emptyset$$ -- since $ \emptyset\emptyset = \emptyset $ and there are 0 elements of $L$

Now since L is $ \emptyset $, then it does not contain $\epsilon$ either. So thus

$$L^\* = \emptyset $$

But that does not seem to be the case. According to the book, $L^0$ is $\\{ \epsilon \\}$ and thus $L^\* = \\{ \epsilon \\}$, for L = $\emptyset$. Where am I going wrong?

# Answer
> 5 votes
You are correct with $L^\* = L^0 \cup \emptyset$.

But $L=\emptyset$ does not imply $L^0 = \emptyset$. Consider $L^i$ to be built incrementally: You start with $\epsilon$ and then add a word from $L$ to the end $i$ times.

If $i\ge 1$ and $L=\emptyset$, this will fail when you try to add the first word, since there are no words in $L$. So here $L^i$ becomes $\emptyset$. But for $L^0$ you never try to take a word from $L$. So the fact that $L$ is empty does not matter, you simply terminate after initialising your word as $\epsilon$.

Thus $L^0=\\{\epsilon\\}$ and $L^\* = \\{\epsilon\\} \cup \emptyset = \\{\epsilon\\}$.

# Answer
> 5 votes
## In a nutshell

It is easy to show why we should define $L^0=\\{\varepsilon\\}$ when $L$ is not empty.

However, the definition $\emptyset^0=\\{\varepsilon\\}$, though nicely consistent, and probably convenient in many cases, could be just arbitrary. It might even be that not defining it should be wiser.

## Why $L^0=\\{\varepsilon\\}$ when $L$ is not empty ?

The proper answer is the one given, maybe too abstractedly, by Pseudonym's comment.

The point is that **you are asking for the meaning of a notation**. The meaning of a notation is whatever the mathematician chooses it to be.

But mathematicians do not do that randomly. They use notations that make things look simple and consistent.

The power notation is often used in mathematics to mean repetition, when dealing with an associative operation (i.e. with a semigroup). The concatenation of languages, here noted explicitly $\bullet$ for clarity, is associative. Hence, we can use the power notation to represent the concatenation of a language $L$ with itself, with $L^1=L$, $L^2=L\bullet L$, $L^3=L\bullet L\bullet L$, and so on, or more generally: $L^{n+1}= L^n\bullet L$.

An interesting aspect of this is that exponents behave exactly as they do for usual exponentiation of numbers: $L^{a+b}=L^a\bullet L^b$ for any pair of positive integer $a$ and $b$.

This shows that there is a morphism from (the semigroup of) the positive integers $\mathbb N\_+$ with addition to (the semigroup of) the powers of any language $L$ with concatenation.

It you now decide to extend the power notation to exponent $0$, you want to preserve as much as possible these morphisms, so as to keep your mathematics consistent. The integer $0$ is the neutral element that extends the additive semigroup of positive integer $\mathbb N\_+$ into the additive monoid of non-negative integers $\mathbb N\_0$.

Hence, to preserve the morphism, you want $L^0$ to denote the neutral element for the concatenation of languages. This neutral element is the language $\\{\varepsilon\\}$, containing only the empty string, since for any language $L$, we have the relations $L\bullet\\{\varepsilon\\}=\\{\varepsilon\\}\bullet L=L$.

Hence, we choose to define, for any language $L$, $L^0=\\{\varepsilon\\}$

Using this definition, the identity $L^{a+b}=L^a\bullet L^b$ remains true even when $a$, or $b$, or both become 0. And it is the only way to achieve that as noted by Pseudonym in his comment.

## But what about $\emptyset^0$ ?

For consistency (again) across languages, this definition should apply to all, including the empty language $\emptyset$. But this argument is not too compelling in the case of $\emptyset$, even though defining $\emptyset^0=\\{\varepsilon\\}$ raises no consistency problem that I know of.

My misgivings about this definition relate to the fact that languages over an alphabet $\Sigma$ actually form a semiring, and the empty language $\emptyset$ is the neutral element of the commutative monoid (for set union) of that semiring. The non-negative integers $\mathbb N\_0$ with addition and multiplication also form a semiring. The power notation is also available (for repeted multiplications). But defining $0^0$ is, to say the least, a risky business, at least when considering the integers as part of larger theories. Hence, I tend to be cautious regarding $\emptyset^0$.

If one considers the axiomatisation of the semiring of languages, such as given by an answer by Pseudonym to another question, or by the semiring axioms in wikipedia, it does not seem possible to deduce anything about $\emptyset^0$ from these axioms. Actually, they cannot provide a definition for it, since this has apparently to be undefined in some models of the theory.

People seem to have found many arguments to justify that $0^0$ should be $1$, but there are also compelling reasons to have it undefined: the function $\lambda x.y. x^y$ is not continuous at the origin. I am wondering whether the argument given in FrankW's answer, and my own consistency argument above, do not run the risk of being similarly disputable.

**Transposing the arguments from the semiring of languages to the semiring of non-negative integers**

My consistency argument is also valid in the semiring $(\mathbb N\_0,+, \times)$ of non-negative integers with addition and multiplication, where the power notation is also used to indicate repeated product, with the possible definition: $\forall a\in \mathbb N\_0, \forall i\in \mathbb N\_+, a^1=a\wedge a^i+1=a^i\times a$.

Then we also have the natural extension from the multiplicative semigroup to a monoid with a neutral element $1$, so that we define $\forall a\in \mathbb N\_0, a^0=1$. And the same consistency argument I suggested for $\emptyset^0$ would then apply to chose to define $0^0=1$.

This goes also for the argument in FrankW's answer. In the semiring $(\mathbb N\_0,+, \times)$, when defining $a^i$, you start with 1 and then you multiply by $a$ repeatedly $i$ times. But if $i=0$, you just stay with 1, and multiply $0$ times by $a$. Hence $a^0=1$. And when $a=0$, since you do not even need to consider $a$ for product, the result is the same. Hence $0^0=1$.

So both our reasonning apply in the case of the semiring $(\mathbb N\_0,+, \times)$, and give the same result: $0^0=1$. But this result is considered wrong for numbers, where $0^0$ should remain undefined (I might be worthwhile investigating deeper the known reasons).

**An unconclusive conclusion**

Actually, the Kleene plus operation, which some people found necessary to define does not need to consider $L^0$: $$ V^+=\bigcup\_{i \in \mathbb N\_+} V^i = V^1 \cup V^2 \cup V^3 \cup \ldots$$

The Kleene star could be defined by adding the empty word $\varepsilon$.

When looking at Kleene algebra (in wikipedia) it seems that the power notation does not play a major role, and I did not see anything that requires defining $\emptyset^0$. But I am no expert on Kleene algebras.

So I have to finish with questions I cannot answer:

* is it really important to define $\emptyset^0=\\{\varepsilon\\}$, beyond the advantage of consistency with non-empty languages ?
* is it really important to define $\emptyset^0$ at all ?
* would it be inconsistent, or problematic, or possibly useful, to define $\emptyset^0=\emptyset$ ?
* could there be compelling reasons to leave $\emptyset^0$ undefined ?

---
Tags: formal-languages
---


# Question
Title: Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?
In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\\{ w\ \\#\ w\ |\ w \in \\{0,1\\}^\*\\}$. However, we proceeded to discuss when a language is recursively enumerable vs machines that are deciders etc, and then started discussing the halting problem.

My question is : given a Turing Machine $M$, is it undecidable to construct its Language $L(M)$, since theoretically there could be an input that never reaches a reject or accept state? (My intuition tells me this reduces to the halting problem).

**EDIT**

If we accept the definition $L(M)$ as the set of *all* strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts (see @d'alar'cop's comment)?

# Answer
In answer to your edited question,

> If we accept the definition $L(M)$ as the set of all strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts?

The answer is yes, we can. In technical terms, this asks whether the language accepted by a TM is recursively enumerable.

Here's how to produce the strings that $M$ accepts. Define an *enumerator* TM, $E$ that acts as follows:

1. Startup: decide on an enumeration of all possible input strings, $s\_1, s\_2, \dotsc$. For example, if the input alphabet was $\\{0, 1\\}$ the strings might be enumerated in order $\epsilon, 0, 1, 00, 01, 10, 11, \dotsc$. It's not hard to see how this could be accomplished. In particular, we could find, for every string $s\_i$, the next string in order, $s\_{i+1}$.
2. Then use what's known as a **dovetail construction** in your enumerator TM $E$: $$\begin{align} &\text{repeat for } i = 1, 2, \dotsc \\ &\quad\text{for } k = 1, 2, \dotsc , i\\ &\quad\quad\text{simulate }M\text{ on } s\_k\text{ for } i\text{ moves}\\ &\quad\quad\quad\text{if } M(s\_k)\text{ accepts}\\ &\quad\quad\quad\quad\text{output } s\_k \end{align}$$

It's not hard to see that every string $s\_i$ accepted by $M$ will eventually be displayed (perhaps several times) by the enumerator TM $E$. In effect, we're running $M$ in (simulated) parallel on all possible strings $s\_i$. Of course, the enumerator $E$ will run forever, but while it's running it will eventually produce any string in $L(M)$ in a finite time, which is just what you wanted.
> 4 votes

# Answer
You can do this for many Turing machines, but not for any Turing machine.

For example you can make a Turing machine whose behaviour is exactly a finite-state machine, i.e. you can program a finite-state machine in a Turing machine. Then the problem for that *given* Turing machine is trivial.

For Turing machines in general this is undecidable, as it is equivalent to the Halting problem. In particular checking whether $w \in L(M)$ is exactly equal to checking whether $M$ halts for $w$.
> 3 votes

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


# Question
Title: Arranging tasks with specific constraints (scheduling)
I have the following problem:

Given a set of tasks and their duration, i need to arrange them taking in consideration some constraints; Here's an example:

Suppose we are scheduling talks in a conferece. Each talk has a duration, and we can use as many rooms as we need. For each room, we have two sessions: one in the morning, and one in the afternoon. Morning one starts at, say, 9 AM and must end *exactly* by noon. The afternoon one starts at 1 PM and must end between 4PM and 5PM.

How do i arrange these talks in sessions in such a way that uses the least amount of rooms possible?

I've researched some scheduling problems, but none of them seem to take into account the constraints i need. I have read about:

http://en.wikipedia.org/wiki/Interval\_scheduling

http://en.wikipedia.org/wiki/Earliest\_deadline\_first\_scheduling

http://en.wikipedia.org/wiki/Flow\_shop\_scheduling

# Answer
> 2 votes
This is actually a *bin packing problem*, rather than a scheduling problem. If I remember correctly (it's been a long time) bin packing is the *dual* of scheduling.

In the most basic kind of bin packing problems each room would be available for exactly three hours, and the goal would be to minimize the total number of three-hour sessions you would consume. Your problem has an extra constraint that rooms come in pairs that are available for 3 and 4 hours.

Bin packing problems are usually NP-complete, but there are some heuristics that tend to work well in practice. For the basic bin packing problem the usual heuristic would be to sort the talks from longest to shortest. Then start placing talks into rooms in that order. For each talk examine the rooms in the same order. Place the talk in the first room where it will fit. You only rent a new room if you have a talk that won't fit in any of the existing rooms.

There's a bit more on the Wikipedia Bin packing page: http://en.wikipedia.org/wiki/Bin\_packing\_problem

And I found this article, which describes some of the approximation algorithm results in this area (as of 1987): http://www.columbia.edu/~cs2035/courses/ieor6400.F07/hs.pdf

---
Tags: algorithms, scheduling
---


title: Question Concerning Big-O Notation

text:
# Question
Title: Question Concerning Big-O Notation
A couple of questions:

1. When choosing $C$ do I have to choose an integer? I see nothing in my definitions preventing fractions, but I haven't seen any in anything I've looked up, either
2. Given $f(x)=O(g(x))$, is there anything preventing me from choosing $f(x)=g(x)$ such as $f(x)=x^2$ and $g(x)=x^2$?

# Answer
1. Usually the definition of $O$ allows for $C$ to be any positive real number.
2. That's a perfectly valid choice.
> 1 votes

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


# Question
Title: Algorithm for finding best combination of elements
Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C.

The types come with expenses: Type A's are the least expensive, and C's are the most expensive, but their expense varies from variable to variable.
For example {A, C, C} may actually be more expensive than {C, A, A} if that first variable happens to be worth more, but we won't know how much the total cost is until we assign the types and run the program.

Also we don't want to go below a certain given total expense (can't make all A's), but get as close as possible to it.

I am trying to minimize the total expense while staying above the threshold. The search space (permutations of variable types) is too large to try all combinations.

Someone recommended sampling via Monte Carlo method earlier.
How can the Monte Carlo method, or Markov-Chain Monte Carlo, be applied to such a problem to find the optimal combination of parameters?
Could a genetic algorithm be used effectively?

# Answer
You normally need to know what heuristic function you have.

Usually, when you use simulated annealing, you don't find a maximum score (or combination that gives the maximum score). What you do is trying to get a score that is better than the current score that you have.

Note that, I find it very strange when you say you want to use simulated annealing for discrete optimization problem like the one you mention. When your problem is discreet, how do you do differential? Thus, how do you know which direction you should proceed with gradient ascent/descent?

There are cases in which a seemingly discreet optimization problem is actually a continuous one in which you can use a customized and modified gradient ascent/descent with an optional simulated annealing. I will refrain from comment further in this particular case.
> -1 votes

---
Tags: algorithms, optimization, sampling, markov-chains, monte-carlo
---


# Question
Title: Minimising two maximum edges in s-t path
I've been trying to solve the following problem:

Problem is the following: Given a graph and a pair of nodes $s$, $t$ you have to find the path from $s$ to $t$ which minimises the sum of its two largest edges.

Here's what i've come up with: I am executing the Prim algorithm with a slight modification. The cost of a node $u$ (i.e what's saved in the heap) is the following: Minimum sum of two largest edges that can lead from $s$ to $u$, where said edges are either on the tree constructed thus far (via Prim) or one of them can be an edge $e=(a,u)$ where $a$ is a node on the tree.

The reasoning of why this should work – I think – is similar to the Prim's algorithm proof. The problem reminds me of the Minimum Bottleneck Tree which can also be solved by MST.

However, the algorithm fails on three test cases. I've checked the source code for errors but I didn't find anything. This means that the error is likely in my algorithm. (Of course, I can post the code if needed.)

Can anyone either show a testcase where the algorithm fails or give a hint in the right direction?

# Answer
> 0 votes
If my assumption on how you handle paths of length 1 is correct (the weight of the path is the weight of the single edge), your example should fail on the graph described by the following adjacency matrix:

$$\begin{matrix} &s&u&v&t\\ s&-&3&4&-\\ u&3&-&3&-\\ v&4&3&-&3\\ t&-&-&3&- \end{matrix}$$

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


# Question
Title: Relationship between an NP-hard problems with the subsets of them (part 2)?
I asked two questions about NP-hard problems here Relationship between an NP-hard problems with the subsets of them? and here https://cs.stackexchange.com/questions/30018/does-this-manner-of-proof-for-being-np-hard-is-true but unfortunately maybe I could not describe my question clearly. Therefore here I will do it. Assume you have a subset-sum problem and there are two subsets of numbers 1- s`ubset A with Integer numbers, 1 to n`, 2- `subset B with Real numbers, 1 to n.` The problem is finding a subset of numbers that the sum of them is equal to S. `1<S <n.`

If we prove that this problem for the subset A is NP-hard whether can we conclude that the problem for the subset B is also NP-hard? I mean since Integer numbers are a subset of Real numbers then can we conclude the above?

I think this is strongly different with false statement "A subset Q of my language P is NP-hard, ergo P is NP-hard".

# Answer
> 3 votes
If problem A is NP-hard and problem B is a generalization of problem A, then problem B is also NP-hard. Here *generalization* means that every instance of A is an instance of B, and an instance of A belongs to A iff it belongs to B. (Technically, the concept of *instance* is a convenient fiction, but I hope you know what I mean. )

---
Tags: complexity-theory, proof-techniques, np-hard
---


# Question
Title: Find the approximate number of messages (n) that need to be tried
Find the approximate number of messages (n) that need to be tried before finding two that had the same message digest (size k) with probability 0.8. You need to find n as a function of k . What is n when k= 2^(160) ?

please guide me how to start to solve this question

# Answer
> 1 votes
This is an application of the Birthday paradox. The explanation of that should get you started.

---
Tags: probability-theory, computer-networks, hash
---


# Question
Title: Are dictionaries and associative arrays the same thing?
With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?

# Answer
As far as I can tell, *associative array* is a newer term, maybe emerging from popular use in dynamic programming languages. In algorithms as an academic field, it seems to denote a generalisation of the *dictionary* but one usually works with dictionaries (probably because most resource characteristics carry over so one does not need to complicate notation).

Citing from theory-leaning \[1, p281\] (bold emphasis mine):

> The *dictionary*, *symbol table*, or simply *search* problem is a fundamental one in computer science: a set of distinct keys is to be organized so that client queries whether or not a given key is in the set can be efficiently answered. More generally, with distinct keys, **we can use binary search trees to implement an *associative array***, where we associate information with each key and can use the kry to store or retrieve such information.

CLRS \[2, p229\] make no mention of associative arrays but define dictionaries:

> We call a dynamic set that supports \[insertion, deletion and membership test\] a *dictionary*.

In the more practically inclined \[3, p361 ff\], the term *symbol table* is used as a synonym for dictionary but defined in a slightly different way:

> A *symbol table* is a data structure for key-value pairs that supports two operations: *insert* (put) a new pair into the table and *search* for (get) the value associated with a given key.

Later, they write:

> \[The conventions "no duplicate keys" and "put on an existing key replaces the old value"\] define the *associative array abstraction*, where you can think of a symbol table as being just like an array, where keys are indices and values are array entries.

Summarising this small literature research (which is not without contradictions) and from a theoretical viewpoint, I'd state the following:

* A *dictionary* is a data structure that implements a (dynamic) *set* with insertion, deletion and membership test.

Mathematically speaking, a dictionary over universe $X$ represents an element of the power set $2^X$ of $X$.
* An *associative array* is a data structure that implements a (dynamic) *mapping* with insertion/update, deletion and retrieval.

Mathematically speaking, an associative array over key universe $X$ and value universe $Y$ represents an element of the set of functions $X \to Y$.

One can thus view a dictionary over universe $X$ as associative array over $(X,\\{0,1\\})$; this closely resembles the indicator function of sets.

I think this fits programmers' reality quite well, but terms may be used differently over there.

**Important:** The usage of the term "array" may suggest $O(1)$ accesses. This can, in general, *not* be expected to be true; at least not in the worst-case and without amortisation arguments. Implementations using hash tables come closest; see here for a discussion about what to expect w.r.t. performance.

---

1. An Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd ed, 2013)
2. Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (3rd ed, 2009)
3. Algorithms by R. Sedgewick and K. Wayne (4th ed, 2011)
> 6 votes

---
Tags: terminology, data-structures, dictionaries, abstract-data-types
---


# Question
Title: Constructing all context-free languages from a set of base languages and closure properties?
One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining them via a small, fixed set of closure properties. Specifically, if we start with the empty language, the language containing the empty string, and the languages of all single-character strings, we can assemble all possible regular languages using union, concatenation, and Kleene star.

Is there a set of base languages and closure properties that can be used to generate all and only the context-free languages? (To clarify: I'm not asking whether you can write regular expressions for all CFLs, which I know is impossible. Instead, I'm wondering whether there is a way to design a regular-expression-like framework for CFLs based on the same basic principles.)

# Answer
> 10 votes
That is possible, but perhaps not exactly in the way you ask. As a start take the Dyck language $D\_2$ of all strings of matching brackets over two pairs of brackets, say $\\{ \[,\], (,) \\}$, or more abstractly $a\_1,b\_1,a\_2,b\_2$.

Then every context-free language can be obtained from $D\_2$ using homomorphisms, inverse homomorphisms and intersection with regular languages. The context-free languages are called "the principal cone generated by $D\_2$", in old books denoted $\mathcal{M}(D\_2)$. See a related question: "Which languages are recognized by one-counter machines?"

In fact, we need only one of each operations (well-chosen). Each CFL can be written $g(h^{-1}(D\_2) \cap R)$, where $g$, $h$ are homomorphisms, and $R$ is a regular language. Intuitively, $R$ is a program of a PDA, $g$ maps each instruction to the letter read, $h$ to the push and pop operations of the stack. Finally $D\_2$ codes proper stack behaviour.

This result is related to the Chomsky–Schützenberger Theorem (or as can be seen in wikipedia, one of them). The statement linked here in wikipedia (a) does not need an inverse homomorphism, while (b) it does not restrict to two pairs of brackets. Theorems of this type are from the area of "Abstract Families of Automata", where Ginsburg and Greibach are important names. A related result by Nivat states that operations of the form $L \mapsto g(h^{-1}(L) \cap R)$ for fixed $g,h,R$ are the finite state transductions.

---
Tags: formal-languages, context-free, closure-properties, regular-expressions
---


title: Prove that $(L^*M^*)^* = (L\cup M)^*$

text:
# Question
Title: Prove that $(L^*M^*)^* = (L\cup M)^*$
I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^\* \subset (L^\*M^\*)^\*\\!$.

We know that $\epsilon, L \in L^\*$ and $\epsilon, M \in M^\*\\!$. Hence $L \subset L^\*M^\*$ and $M \subset L^\*M^\*\\!$, so we can write this as $L^\*M^\* = (L \cup M) \cup X $. From this it follows that $(L\cup M)^\*\subset (L^\*M^\*)^\*\\!$.

# Answer
> 0 votes
Your proof seems elegant to me. It fits in about three sentences, which is probably about as good as you're going to get, for something like this. I don't think you're going to find anything cleaner. Or, at least, it's hard to suggest what you would find cleaner, without knowing your tastes and what you find inelegant about this proof.

One possible improvement (albeit a very slight one) would be to change the second half of your second sentence to "so we find that $L \cup M \subset L^\* M^\*$".

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


# Question
Title: Can a Big-Oh time complexity contain more than one variable?
Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct families. Would it be acceptable to call the complexity of an algorithm $O(n * m)$ or $O(n + m)$ (depending on if we use a naive or an optimized algorithm)?

On a similar vein, let us presume the algorithm we choose actually requires two stages - a setup phase on the first string which allows us to process any number of other strings without incurring that initial cost. Would it be considered appropriate to say it has a $O(n)$ construction followed by any number of $O(m)$ calculations?

Would it be appropriate to just call them $O(n)$ because both calculations are linear?

# Answer
Yes, of course. This is fine and perfectly acceptable. It is common and standard to see algorithms whose running time depends upon two parameters.

For instance, you will often see the running time of depth-first search expressed as $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. This is perfectly valid. The meaning of this is there exists a constant $c$ and numbers $n\_0,m\_0$ such that the running time of the algorithm is at most $c \cdot (n+m)$, for all $n\>n\_0,m\>m\_0$. In other words, if the exact running time is $f(n,m)$, we say that $f(n,m) = O(n+m)$ if there exists $c,n\_0,m\_0$ such that $n\>n\_0$ and $m\>m\_0$ implies $f(n,m) \le c \cdot (n+m)$.

Yes, it is perfectly appropriate and acceptable to say that the first stage takes $O(n)$ time and the second stage takes $O(m)$ time.

Important: make sure you define what $n$ and $m$ are. You can't say "this is an $O(n)$ time algorithm" without specifying what $n$ is. If $n$ isn't specified in the problem statement, you need to specify it. For instance, see graph algorithms, where we typically define $n = $ # of vertices and $m = $ # of edges.

As far as whether you can call them $O(n)$ time, no, of course not -- unless you somehow know that $m = O(n)$. Of course, if you know that $m = O(n)$, then it follows that $m+n = O(n)$, so an $O(m+n)$ time algorithm is also an $O(n)$ time algorithm. But if there is no guarantee that $m = O(n)$, then you cannot call it an $O(n)$ time algorithm.

This is basic stuff. You'll find it all over algorithms textbooks.
> 20 votes

---
Tags: time-complexity, asymptotics, landau-notation, notation
---


title: How to simplify the sum over 1/i?

text:
# Question
Title: How to simplify the sum over 1/i?
With the recurrence relation: $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$

The "sum for all levels" in the recurrence tree is: $$ \sum\_{i=0}^{\log n -1} \frac{n}{\log n - i} = \sum\_{i=1}^{\log n} \frac{n}{i} = n \sum\_{i=1}^{\log n} \frac{1}{i}$$

Inside the analysis of the recurrence, $\sum 1/i$ appears and then bounded by $\Theta(\log\log n)$. Why is this?

# Answer
> 5 votes
If you consider the last term in general, $\sum\_{\[1\leq i \leq \log n -1\]} \frac{1}{i} $ as $$ \sum\_{\[1\leq i\leq k\]} \frac{1}{i} $$ In this way, you can establish a bound using a integral generalization for this sum: $$ \sum\_{\[1\leq i\leq k\]} \frac{1}{i} \leq \int\_{0}^{k} \frac{1}{x} dx = \ln (x)|\_{0}^{k}= \ln(k) - \ln(1) = \ln(k)$$ But, in your problem, as we know, $k = \log n - 1$, so for above:

$$\sum\_{\[0\leq i \leq \log n -1\]} \frac{1}{i} \leq \ln (\log n - 1)\leq \ln \log n$$

For that, $$\sum\_{\[0\leq i \leq \log n -1\]} \frac{1}{i} = O(\ln\log n)$$

But, you can exhibit a constants to achieve, $\Theta(\log\log n)$.

# Answer
> 4 votes
$\sum\_{i=1}^k\frac{1}{i}$ is the $k$th harmonic number, which is $\Theta(\log k)$.

---
Tags: asymptotics, recurrence-relation, discrete-mathematics
---


# Question
Title: What is the significance of reverse polish notation?
I teach computing to 18 year olds. After having reverse polish notation (RPN) explained to them, one asked why is it significant enough to be in the public exam. I explained the historical significance of '70s calculators, but this failed to really address the issue.

So, are there any modern practical or theoretical applications of RPN?

# Answer
I've used RPN several times for rapid prototyping, e.g. of programs that have to read and interpret a user-supplied mathematical expression.

Whereas regular mathematical notation would require at least a recursive parser (think brackets, operator order, etc...), an RPN parser is basically a stack with a `switch`-like statement. I guess it's this combination of simplicity and expressive power that led HP to use it initially.

This is, however, usually for rapid prototyping and for convenience. I would never assume that a user can, or wants to, understand RPN.
> 11 votes

# Answer
Just to expand the previous answers/comments: don't forget that RPN is *alive and on great form* ... indeed it is currently used in **stack machines** like the Java virtual machine.

From Wikipedia: *"... a stack machine implements a stack with registers. The operands of the arithmetic logic unit (ALU) are always the top two registers of the stack and the result from the ALU is stored in the top register of the stack. 'Stack machine' commonly refers to computers which use a Last-in, First-out stack to hold short-lived temporary values while executing individual program statements. The instruction set carries out most ALU actions with postfix* (**Reverse Polish notation**) *operations that work only on the expression stack, not on data registers or main memory cells ..."*

The advantages/disadvantages of such approach are also described in the Wikipedia article.
> 9 votes

# Answer
With regards to calculators: See What is RPN?

* Benefits: RPN saves time and keystrokes. You avoid using and keeping track of parentheses while doing calculations. The process is similar to the way you learned math on paper.
* You can see the intermediary results as you perform your computations rather than just the answer at the end. This is extremely helpful for learning the logic. Math teachers are using this feature to improve student understanding of mathematics.
* An intermediate result allows the user to check the answer and correct errors more easily. It's easier to follow the stream of calculation. The user defines the priority of operators.
* RPN is logical because the user first gives the number and then tells what to do with it.
> 5 votes

# Answer
Forth and PostScript (and thus PDF which IIRC started as a binary encoding of a subset of PostScript) are more well known postfix languages that HP pocket calculator one.

Then it is also a relatively common choice as intermediate representation in simple compilers.

The simpler VM tend to have also a postfix "machine" language.
> 5 votes

# Answer
Your student was absolutely right. Reverse Polish Notation is not significant enough in computer science to be worth spending very limited class time on it. Instead, there are so many other wonderful conceptual ideas you could have taught, with deep intellectual ideas: stable marriage, cake-cutting, diagonalization and undecidability of the halting problem, interactive proofs and zero-knowledge proofs, etc., etc. Yes, all of those can be made accessible to 18-year-olds.

And, I do hope you praised your student for being brave enough to ask the question! They had to put themselves on a ledge to raise the issue. It speaks well for your teaching style that they felt comfortable asking you this question.
> 3 votes

# Answer
As the name indicates, Reverse Polish Notation, or Direct Polish notation, are notations. They are syntax for representing something, and actually efficient syntax if you consider memory requirements. What they represent are rooted trees, which can be formulae, abstract syntax trees (AST), and other kinds of entities, that anyone has a constitutional right to consider absolutely useless.

Occasionally, one has to store such entities on file. For example there are systems that may edit or transform programs as AST, and may need to store such representations. Polish Form is convenient. It has limited readability for humans, especially for large trees, but it is a very convenient representation for machines.

Another aspect of it is that I believe the study of trees and their elementary uses and representation, as well as associated devices (stacks), to be pedagogically useful as an introduction to future studies of more advanced concepts (syntax, parsing, logic, linguistics, ...).

It has also the advantage of being conceptually rather simple, and easy to experiment on paper. It is also a nice occasion to discuss syntax and the fact that syntax is representation, and that representations may vary, while representing the same thing, and that different representations may be used depending on the need to be met (space optimization, easy modification, human readability, computer readability, ...).

But I am surprised that this question, and its answers, are considering only RPN, and none considers direct polish notation.

It is certainly excellent that students ask. But answering such question always has diverse aspects. Is it useful for the knowledge itself? I think it is. Is it useful as pedagogical exercise? I think it is, but that depends much on the intended audience, and only the teacher can assess what it is able to understand. Is it useful to understand some conceptual issues? I think it is, but again it depends on the teacher's assessment of what concepts can be explained to their students.
> 3 votes

# Answer
Reverse Polish Notation was a good tool in my education for understanding parse trees and tree data structures in general. It's also useful if anyone has any interest at all in programming in any of the Lisp family of languages (Clojure, emacs-lisp, scheme etc..).
> 1 votes

---
Tags: terminology, education
---


# Question
Title: How are Signed integers different from unsigned integers once compiled
How are Signed integers different from unsigned integers once compiled?

I already know about twos compliment and the like but my question is how can you tell the difference when looking at 8 bit integers when in binary eg `10000001` if this is a signed integer it would be equal to -127 but if it is unsigned it would be equal to 129. So my question is how can you tell the difference when presented with just 8 binary bits.

And also how are signed integers different from a compilers perspective, and how can a CPU tell the difference while performing arithmetic on them

# Answer
> 6 votes
For simple types, you can't tell by looking at the bits in memory. Because the source specifies that the data is of a particular type, the compiler generates code that interprets the bits in memory as representing data of that particular type. In particular, in cases where different CPU instructions are needed (e.g., integer vs floating point), the compiler will generate instructions appropriate for the datatype in question. Note that, by the magic of two's complement, signed and unsigned integers are added, subtracted and multiplied by the same instructions. (That is, if you compute $z=x\times y$ believing that $x$ and $y$ are unsigned and I then tell you that they're actually signed, all you need to do is interpret $z$ as being signed and you have the right answer.)

Depending on the language, objects may or may not have some sort of tag that says what class the object instantiates. But the same considerations as above apply: there's no physical difference in memory between the tag and any other datatype that happens to have the same number of bits.

# Answer
> 8 votes
There is no way to tell if 8 bits in memory are a signed integer, an unsigned integer, a character, or part of a bigger data. The knowledge is put in the instructions.

As stated by David Richerby, two's complement makes signedness transparent in most operations (addition, substraction, multiplication), but some are different: the bitwise shift may preserve or ignore the sign bit. Some processors implement arithmetic shift to preserve sign bit (acting like a division, even on negative numbers) and logic shift (which is suitable for unsigned integers). When you compile your source code, the compiler knows the type of your data, and generate the program with the instruction that fit with your use-case.

Please note that some processors implement only one type of bit shifts. In such case, to keep the same behavior, the compiler will add some extra instructions to do the same work (based on the compiler's knowledge of the data types). Some languages may avoid such extra work on the compiler by stating something like

> The result of E1 \>\> E2 is E1 right-shifted E2 bit positions. \[...\] If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Source : C language : ISO/IEC 9899:TC2 section 6.5.7 (Bitwise shift operators)

Type and signedness aren't part of the data itself. The knowledge was already used to generate the instructions that use the data according to their actual type. For dynamic type evaluation (at runtime, see dynamic programming language), some kind of tags (many implementations are possible) are added in the data structures to identify their type, and use the appropriate code to handle it.

---
Tags: compilers, integers, arithmetic
---