# Question
Title: Algorithm for estimating function maximizing parameters
I'm trying to find parameters $\omega, \alpha,$ and $\beta$ which maximize

$$ \sum\_{i=1}^m{\left\\{ -\ln(v\_i) - \frac{r\_i^2}{v\_i} \right\\}} $$

where

$$ v\_i = \omega + \alpha r\_{i-1}^2 + \beta v\_{i-1}^2 $$

Since numerical values for $r\_i$ and $v\_1$ are given my first thoughts were to use the normal equation

$$ \Theta = (X^TX)^{-1}X^Ty $$

This I realized quickly wouldn't work because there are no observed values of $v$ to fill $y$ with. I similarly considered something along the lines of gradient descent but then again I ran into the same problem. I only have $v\_1$ as a starting point but no observed $v\_2, v\_3$ etc. I've also found my way on the Levenberg-Marquardat wikipedia page but then again I came up empty because I can't figure out how to produce (independent, dependent) bundles under these conditions.

The problem I'm basically trying to solve is that of estimating the three parameters of a GARCH(1,1) model ($v\_i$ above).

MathLab offers tools which can estimate these parameters for me but what I'm trying to do is understand how the under-the-hood algorithm works in coming up with these numbers. Even excel's solver can figure out these parameters given an initial guess but I have not been able to find how it actually works. I understand that starting from an initial guess it uses an iterative method to arrive at a solution but I can't figure out how it updates the parameters at every run.

# Answer
You have a function $f:\mathbb{R}^3 \to \mathbb{R}$, which accepts three real numbers as input and produces a real number as output. You want to find values $\omega, \alpha, \beta$ that maximize $f(\omega, \alpha, \beta)$.

This is a standard problem in mathematical optimization, and there are a variety of techniques for solving this problem.

* **Black-box methods.** The methods that are easiest to use treat $f$ as a complete black box: all we need is a way to evaluate $f$ at any input of our choice. Example methods include hill climbing, coordinate descent, (well, in this case it will be coordinate ascent, since you want to maximize $f$), gradient descent (well, in this case it will be gradient ascent, since you want to maximize $f$), Newton's method, conjugate gradient methods, and more.
* **Black-box, plus derivatives.** Some of these methods can be sped up significantly if we have an efficient way to evaluate each of the partial derivatives of $f$ at any input of our choice. Sometimes, if $f$ has a simple representation, we can compute the partial derivatives of $f$ algebraically, which then gives us a way to evaluate these functions at any desired input. The reason this speed things up is that some of the black-box methods effectively end up approximating the partial derivatives or 2nd partial derivatives (e.g., the gradient or Hessian matrix) as part of the process; if you have a faster way to compute them directly, then those methods become more efficient and more effective.
* **Dedicated methods.** There are other methods available if the function $f$ has a particular algebraic form, e.g., linear programming, convex optimization, and more. These probably won't apply to you, so they can be safely ignored in your situation.

Many tools, like MathLib, include built-in libraries to apply these methods for you.

In your case, the function $f$ is given by $f(\omega, \alpha, \beta) = \sum\_{i=1}^m{\left\\{ -\ln(v\_i) - \frac{r\_i^2}{v\_i} \right\\}}$ where $v\_i = \omega + \alpha r\_{i-1}^2 + \beta v\_{i-1}^2$. But those details aren't important; what's important is that, given $\omega, \alpha, \beta$, you can evaluate $f$ to learn the value of $f(\omega, \alpha, \beta)$. That allows you to apply black-box optimization methods.

One generic issue to be aware of is that many of these methods may only produce a local optimum, not a global optimum. There are a variety of heuristics for dealing with this, but generally none that are guaranteed to work in all cases. Often, the methods are fairly sensitive to the choice of starting point, so if you have a good guess at a value of $\omega, \alpha, \beta$ that is likely to be near the optimal value, then starting the methods from there can be helpful. Also, it can be helpful to apply the methods multiple times, from different (random) starting points and take the best observed over all iterations.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Context-sensitive grammar for the language of words concatenated with themselves
I'm looking for a context-sensitive grammar that describes the following language: $L = \\{ ww \mid w ∈ \\{a,b\\}^{\ast}, |w| ≥ 1\\}$ .

I've got problems with the fact that no rules such as $X \to \varepsilon$ are allowed and therefore I can't place any nonterminal indicating the "middle" of the word. Is there any trick to the problem?

# Answer
Indeed, there is a simple trick that allows you to add extra information at a certain position: just replace a letter adjacent to the position and mark it with the information, and the original letter.

In your example, have a nonterminal $M$ for the middle, but as it can not be deleted, it also counts as a normal letter. Thus we have two copies $M\_a$ and $M\_b$ to indicate the letters replaced. In the end of the derivation the markers should be replaced by their letter content, by simple productions like $M\_a\to a$.

In most cases the application of $M\_a\to a$ needs to be performed at the end of the derivation process. In some constructions this does not need to be "timed": when the $M$ disappears too soon, the derivation cannot find a proper position and the process will not stop successfully. In other cases one does need a kind of control. This is sometimes done by introducing a nonterminal as a signal that moves along the letters. Again, this signal should also carry a terminal otherwise you end up in the same problems.

Moving information around is easy in so-called monotonic grammars ($\alpha\to \beta$ with $|\alpha|\le\beta|$) using rules like $XA \to AX$, which can be seen as $X$ jumping over $A$. For proper context-sensitive grammars one needs to split this in three steps: $XA \to XA^X, XA^X\to AA^X, AA^X\to AX$. in each production one letter is changed in a proper context. It takes quite some imagination to see this process does not interact with other parts of the derivation. E.g., what happens when the $A$ in the last step is first involved in another derivation step?

This might not work for very short words, when there is more information than positions available. The most simple solution to that is to ignore short strings in your construction, and generate them separately.
> 6 votes

# Answer
Short default answer: come up with an LBA which accepts the language and use the simulation used to prove that context-sensitive grammars and LBA define the same set of languages. But that is of course not what you are after.

In this specific case, try to think of using a right-linear grammar for $\Sigma^\*$ twice, one for the left and one for the right half. All you have to ensure that both grammars derive "in sync".

This can be done by swapping around a control token. That is to say, the left grammars picks a rule, generates the fitting control token and passes it to the right grammar. The right grammar sees the control token and executes the fitting rule. Note that you can also implement two-way communication in this way, but it's not necessary here.

There is one problem with context-sensitive grammars: they can never delete non-terminals (except $S \to \varepsilon$ if the empty word is in the language). Therefore, we have to create only as many non-terminals as we are going to need; none can be redundant.

One way to achieve this is to use the same trick as for certain proofs about LBA: generate all non-terminals you are going to need *first*, i.e. prepare the "tape". Later, "move around" on that tape. Only "at the end", replace all non-terminals with terminals.

> So let $G=(N, \Sigma, \delta, S)$ with $\Sigma = \\{a,b\\}$ (the construction readily extends to larger alphabets) and $N$, $\delta$ given by the following rules.
> $\qquad \begin{align} S &\to \hat{X}\_l S' X\_r \mid aaaa \mid abab \mid baba \mid bbbb \mid aa \mid bb \mid \varepsilon \\ S' &\to X\_l S' X\_r \mid X\_l \hat{X}\_r \end{align}$
> are the rules for generating the "tape". Note that the hat denotes the "head position" and indices $l,r$ denote which half of the word a non-terminal belongs to. The short words are generate thus in order to safe some rules below. Now we need rules to derive one symbol in the left part:
> $\qquad \begin{align} \hat{X}\_l X\_l &\to X\_\gamma \hat{X}^\gamma\_l \\ \hat{X}\_l X\_\alpha &\to X\_\gamma X^\gamma\_\alpha \end{align}$
> for all $(\alpha, \gamma) \in \Sigma^2$. Note how we use the upper index to carry the generated symbol to the right. $X\_a$ and $X\_b$ are "final" non-terminals which will only be used for moving the control token around and to derive terminals later. Note furthermore that the second rule is (only) used for the last symbol of the right half.
> For moving the carry to the right half, we have to move past both remaining $X\_l$ and already generated $X\_\alpha$:
> $\qquad \begin{align} \hat{X}^\gamma\_l X\_l &\to \hat{X}\_l X^\gamma\_l \\ \hat{X}^\gamma\_l X\_\alpha &\to \hat{X}\_l X^\gamma\_\alpha \\ X^\gamma\_l X\_l &\to X\_l X^\gamma\_l \\ X^\gamma\_l X\_\alpha &\to X\_l X^\gamma\_\alpha \\ X^\gamma\_\alpha X\_\beta &\to X\_\alpha X^\gamma\_\beta \end{align}$
> for all $(\alpha, \beta, \gamma) \in \Sigma^3$. Now, once the carry reaches the right control token, we have to mimic the rule used on the left:
> $\qquad\begin{align} X^\gamma\_l \hat{X}\_r &\to X\_l \hat{X}^\gamma\_r \\ X^\gamma\_\alpha \hat{X}\_r &\to X\_\alpha \hat{X}^\gamma\_r \\ \hat{X}^\gamma\_r X\_r &\to X\_\gamma \hat{X}\_r \\ \hat{X}^\gamma\_r &\to X\_\gamma \end{align}$
> for all $(\alpha, \gamma) \in \Sigma^2$. Note that the first rule is used for the first symbol of the right half, and that the last rule can only be used for the very last symbol, otherwise the derivation never terminates. Now we only need the terminating rules
> $\qquad X\_\alpha \to \alpha$
> for all $\alpha \in \Sigma$ and we are done. These rules, too, can only be applied after everything (to the left) is done, otherwise the derivation will not terminate.
> Note that this grammar is ambiguous. Not only can can $X\_\alpha \to \alpha$ (safely) be applied anywhere to the left of the left "head" at any time, but there can also be multiple carries underway at the same time. Since they can never overtake each other the correct order is maintained.
> One remark has to be made still: above grammar is *not* context-sensitive as many rules changes *both* of the symbols on the left-hand side. This is not allowed for context-sensitive grammars. Luckily, we can simulate any rule $R$ of the form
> $\qquad A B \to C D$
> by
> $\qquad \begin{align} A B &\to A Y\_R \\ A Y\_R &\to X\_R Y\_R \\ X\_R Y\_R &\to X\_R D \\ X\_R D &\to C D \end{align}$
> so we are good and can work with the smaller grammar. Showing that interference between multiple such simulations does not hurt is left as an exercise.

Do you see how to extend this to $L\_k = \\{ w^k \mid w \in \Sigma^\*\\}$? Does it also work for $L = \bigcup\_{i\geq 1} L\_k$? Can you use the same construction for any $L^k$ for regular $L$?
> 1 votes

# Answer
Although I don't know how the context-sensitive grammar will look like, you can circumvent your problem with the symbol $X$ as follows.

You know that your concatenated words $w$ must be at least of length $|w| \ge 1$. Hence, you could simply "encode" those $\varepsilon$-rules of your grammar by some rules like: $$aXa \to aa,\ \ aXb \to ab,\ \ bXa \to ba,\ \ bXb \to bb$$

Though, I cannot yet see the overall solution, because to my mind it seems like your left-hand sides of your grammar rules potentially get arbitrarily long, because I think you would try to consider the prefixes of $w$ somehow in your rules.
> 0 votes

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


# Question
Title: Why do some filesystems have fragmentation and others don't?
I try to understand why fragmentation is a problem for NTFS and FAT but not when using inodes. In all cases, files are not necessarily stored in a contiguous fashion so I don't see the problem for the former two.

So where is the crucial difference?

# Answer
I think the term *inode* is misplaced here. I am unaware of any way in which Inodes have anything to do with optimizations to reduce disk fragmentation. The term *inode* goes back to Unix Version 1 from 1971. It was not until the Berkeley Fast File System in BSD 4.2 in 1983 that anything significant was done to combat disk fragmentation. In Unix systems the term *inode* refers to the data structure that holds all the metadata for a file (its length, permissions, owner, and the pointers to the data blocks for the file (arranged as a tree in most Unix file systems since 1983.) The file name is *not* stored in the inode. Rather directory entries contain the name and an inode number.

NTFS has a data structure analogous to the inode, that contains similar information, and similarly does not contain the file name. In NTFS this structure is called a *master file table entry*. *Given the similarities between an inode and NTFS's master file table entries, I can't see any impact on any kind of fragmentation.* FAT also has a similar data structure, the *directory entry*. Unlike NTFS and Unix inodes, the FAT directory entry contains the file name along with all the other file information. Putting the file name with the rest of the file metadata has both positive and negative consequences, but *I can't figure out how this difference would have any bearing whatsoever on disk fragmentation.*

In fact FAT has a subtle (and not very important) advantage over NTFS and most Unix file systems with inodes. In systems with inodes (or NTFS's master file table), the inodes are allocated in inode tables, and in some systems (like Linux's ext2) you had to choose the ratio of inode tables to data blocks. This meant that if you had more small files than you expected you might run out of inode entries even though more data space was still available, and if you have larger files than expected you might run out of data space even though there is empty space allocated for unused inode tables.

Every filesystem has disk fragmentation. Your *perception* of which actually suffer from real problems may not be completely accurate. For example: NTFS has an interface specifically designed to make it easier to write user-level defragmentation utilities that can keep serving file requests while defragmentation is going on, while ext4 (the most commonly used file system on recent Linux systems) does not. That doesn't necessarily mean that ext4 has less disk fragmentation than NTFS, it just means that if an ext4 file system gets fragmented there is nothing you can do about it. Both ext4 and NTFS have a number of optimizations to reduce the probability of serious disk fragmentation problems.

You should think of a filesystem as a data structure with a set of algorithms for modifying the data structure. As with any other data structure the designer needs to trade off a variety of different desirable and undesirable traits.

One of the decisions a filesystem implementation needs to make is block size. With larger blocks larger chunks of data are guaranteed to be adjacent. On the other hand, it is rarely the case that a filesystem allows a block to be used by more than a single file at a time (the FreeBSD UFS2 system (c. 2003) being an exception), so if you choose larger blocks but then have many small files those files are going to be spread further apart on the disk (this is so called *internal* fragmentation.)

Almost every modern file system (including NTFS, HFS+ (Mac), UFS2 (FreeBSD), ZFS (Solaris) and ext4 (Linux)) has a variety of heuristics included to help reduce the number of disk-head movements required during a complete file access. These include allocating a file's data near its inode, locating the inode near the directory that contains it, and allocating adjacent blocks for data writes that are known to be longer than a block. Journaling file systems try to combine together many small writes into larger chunks that can be written to adjacent blocks.

Some file systems implement *delayed allocation*, which permits them to decrement the free-space counter for the disk when the space is requested, but delay choosing which block to write the data to until the time at which the data needs to be flushed from data to memory. This requires coordination between the file system and other parts of the operating system. The wikipedia article does not list NTFS as performing this optimization (and FAT system almost certainly don't bother with anything that sophisticated.)

Another thing you should take into account is whether the file system is going to be used on a hard disk or on a solid-state drive (or flash drive). Disk fragmentation does not matter for solid state drives (because there are no mechanical delays, so every block is equally fast to access). On the other hand for solid-state/flash drives *wear leveling* matters a lot.
> 5 votes

---
Tags: operating-systems, filesystems, storage
---


# Question
Title: Find similar vector by Locality Sensitive Hashing
I have many vectors in my database. They are in high dimensions such as:

* $v\_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$
* $v\_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$
* ...

I will use Hamming distance to calculate their difference: The difference between $v\_1$ and $v\_2$ is $4$ because elements $3$ and $4$ are the same and others are difference.

Now, I want to use Locality Sensitive Hashing (LSH) to put those vectors into different bins.

> What kind of hash function can I use for this case?

I have read some article about universal hash function, but I am not sure can I use it and how to ensure that the probability for the similar vectors going to the same bin is higher than those non-similar one.

Here is the way that I think how should I use the universal hash function for my task.

I will first divide those high dimensions vectors into sub-vectors: $$x : 23, 23 \\; | \\; 1, 33 \\; | \\; 103, 219 \\; | \\; \dots$$

sub1-x : 23 23
sub2-x : 1 33
sub3-x : 103 219

The following function will be used for each sub-vector: $$sum\_{i=0}^{r} a\_{i}x\_{i} \mod m$$

Basically this is a dot product, a = {a\_1, a\_2, ... a\_i}, x = {23, 23, 1, 33, 103, 219 ...}, m is a prime.

* Different combination of {a} will form a different hash table, one hash table is used for one sub-vector.
* I can now hash the data into bins, **but the question is**
> Is this an LSH method? I don't know that two similar vectors will go into the same bin with a high probability.

# Answer
> 4 votes
Yes. This is one plausible method, if you want to find pairs of vectors that are very close to each other. Two vectors that are close in Hamming distance are likely to end up in the same bin at some point.

Suppose two vectors $v,w$ agree in fraction $p$ of their coordinates (where $0\le p \le 1$). Then, heuristically, if we look at a pair of coordinates, the probability that $v,w$ agree on those coordinates is $p^2$; and if we choose those two coordinates for hashing, then $v,w$ will end up in the same bin. If you hash each vector $n$ times, choosing a random pair of coordinates each time, then with probability $1-(1-p^2)^n$, there will be at least one time when they show up in the same bin.

For instance, if two vectors agree on half of their coordinates, and if you hash them 10 times, then 94% of the time they will end up in the same bin for at least one of those 10 hashes.

To know how well it will work on your particular application, you may need to try it (or at least work out the parameters of how close vectors will be, when they are close; how many dimensions they have; how many times you will hash them; etc.).

---
Tags: hash, databases, hash-tables, string-metrics
---


# Question
Title: Computing every possible sum of integers taken from different sets
I'm trying to proove $NP$-membership for a problem from the following certificate. I have $n$ sets of integers : $$(S\_i)\_{i \in \\{1,\dots,n\\}}$$ Each set has a number $m\_i$ of integers. I make "combination" from those sets by taking at most one element in each set. A "combination" has between $0$ and $n$ elements (assuming sets are not empty). A "combination" has a value : the sum of its elements. I have to compute the sum of every possible "combination" values, and look if it is greater than a given value. An analytical formula would be nice, but I'm not sure it exists. Otherwise, do you think this sum is easily computable ?

# Answer
$C\_0=\\{0\\}$, $C\_{k} = C\_{k-1} \cup \\{ x+y \mid x\in C\_{k-1}, y\in S\_k \\}$.
> 1 votes

# Answer
Let $x\_{ij}$ be the $j^{th}$ element of $S\_i$ and let $S$ denote the sum of all combinations. We consider $S$ as $$S = \Sigma \\;x\_{ij} \cdot w\_{ij}$$ where $w\_{ij}$ is the number of combinations that contain $x\_{ij}$.

Consider an arbitrary element $x$ of $S\_1$. There are $(m\_2+1) \cdot (m\_3+1) \cdots (m\_n+1)$ possible combinations that contain $x$ (i.e.: pick any of the $m\_2$ elements of $S\_2$ or none, pick any of the $m\_3$ elements of $S\_3$ or none, etc...). So, in general, $w\_{ij} = \left(\Pi\_{k=1}^n(m\_k+1) \right)/(m\_i+1)$.

Note: This is assuming that the question is asking for the sum of the values of all combinations. If the real question is the sum of the values of all *distinct* combinations, this will not work.
> 0 votes

---
Tags: algorithms, sets
---


# Question
Title: Number of multisets such that each number from 1 to $n$ can be uniquely expressed as a sum of some of the elements of the multiset
**My problem.** Given $n$, I want to count the number of valid multisets $S$. A multiset $S$ is valid if

* The sum of the elements of $S$ is $n$, and
* Every number from $1$ to $n$ can be expressed uniquely as a sum of some of the elements of $S$.

**Example.** For example if $n=5$ then $\\{1,1,1,1,1\\}, \\{1,2,2\\}, \\{1,1,3\\}$ are valid.

However, $S=\\{1,1,1,2\\}$ is invalid because 2 can be formed by both $\\{1,1\\}$ and $\\{2\\}$ (i.e., 2 can be expressed as both $2=1+1$ and $2=2$), so the second condition doesn't hold. Similarly 3 can be formed by $\\{2,1\\}$ and $\\{1,1,1\\}$.

$S=\\{1,2,4$} is also invalid because all numbers from $1$ to $5$ can be uniquely made, but the sum of the elements of $S$ is not $5$.

---

I've tried to find a good algorithm for this problem for quite some time but cannot solve it. It is from codechef. I've seen some of the submitted solutions but I still couldn't get the logic for solving the problem. **NOTE:** The time limit for the question is 10 seconds and $n\<10^9$

For a multiset I will use the notation $S = \\{(a\_1, c\_1), (a\_2, c\_2) ... \\}$ $a\_i\<a\_j$ if $i\<j$, which means $a\_i$ occurs $c\_i$ times in multiset S.

Till now I have drawn some conclusions

* First element of the required sorted multiset should be $1$
* Let $S=\\{1,a\_2 \cdots a\_k\\} | a\_1 \leq a\_2\cdots \leq a\_k $ be a set following the two properties then $\forall r\<k \ \ a\_{r+1} = a\_r \text{ or } (\sum\_{i=0}^ra\_i) + 1$
* Let $S=\\{(1,c\_1),(a\_2,c\_2) \cdots (a\_k,c\_k)\\} | a\_1 \leq a\_2\cdots \leq a\_k$, where $a\_i$ is occurring $c\_i$ times, follows the required properties then from the above conclusion we can say that $\forall i \ a\_i|n+1$ and $a\_i | a\_j$ if $j \> i$ .
Proof: $a\_{i+1} = (a\_ic\_i + a\_i -1 ) + 1 \Rightarrow a\_i | a\_{i+1}$
* Now consider $S=\\{ \underbrace{1,1 \cdots 1}\_{d-1},d,d \cdots d,dm\_1, dm\_1 \cdots dm\_1,dm\_2, dm\_2 \cdots dm\_2, \cdots \\}$ i.e. all the subsequent numbers after 1 will be a multiple of $d$. So let $f(n)$ be the count of such multiset possible then $f(n) = \sum\_{d|n+1, d\neq 1} f(\frac{n-(d-1)}{d})$ where I am summing over all possible number of $1's$($=d-1$). In other terms $f(n-1)=g(n)=\sum\_{d|n,d \neq n}g(d)$

Finally my problem is reduced to this - find $g(n)$ in an efficient way so that it doesnt exceed the time limit.

# Answer
> 2 votes
Here is what the fastest solution is doing. It is indeed computing your function $$ g(n) = \sum\_{\substack{d \mid n \\ d \< n}} g(d), \quad g(1) = 1. $$ Given $n$, we factor it (see below) and then compute all factors (see below) $f\_1,\ldots,f\_m$ in some order such that $f\_i|f\_j$ implies $i \leq j$ (property P). We now compute $g$ according to the formula by going over the factors in the given order. Property P ensures that when we compute $g(d)$, we have already computed $g(e)$ for all non-trivial factors $e$ of $d$. There is also an optimization (see below).

In more detail, we go over the factors in order, and for each factor $f\_i$, we find all of its non-trivial factors by checking which of $f\_1,\ldots,f\_{i-1}$ divides $f\_i$.

**Factoring:** Preprocessing: we make a list of all primes below $10^9$ using the Eratosthenes sieve. Given $n$, we simply use trial division.

**Generating all factors:** This is done recursively. Suppose $n = p\_1^{k\_1} \cdots p\_t^{k\_t}$. We run $t$ nested loops $l\_1 \in \\{0,\ldots,k\_1\\},\ldots,l\_t \in \\{0,\ldots,k\_t\\}$, and output $p\_1^{l\_1}\cdots p\_t^{l\_t}$. You can prove property P by induction.

**Optimization:** Since the program is run on several inputs, we can use memoization to save time across different inputs. We only memoize small values (up to $10^5$), and this allows us to store all memoized values in an array. The array is initialized with zeroes, and so we can tell which values are already known (since all computed values are positive).

---

If the prime factorization of $n+1$ is $p\_1^{k\_1},\ldots,p\_t^{k\_t}$, then $f(n)$ depends only on $(k\_1,\ldots,k\_t)$, and in fact only on the sorted version of this vector. Every number below $10^9$ has at most $29$ prime factors (with repetition), and since $p(29)=4565$, it seems feasible to compute $f$ (or rather $g$) for all of them, recursively. This solution could be faster if there were many different inputs; as it is, there are at most $10$.

It is also possible that this function, mapping partitions to the corresponding $g$, has an explicit analytic form. For example, $g(p^k) = 2^{k-1}$, $g(p\_1\ldots p\_t)$ is given by A000670, and $g(p\_1^2 p\_2\ldots p\_t)$ is given by A005649 or A172109.

# Answer
> 1 votes
OK, so you have a recurrence relation for $g(\cdot)$ (see the end of your question).

At this point it seems like a natural approach would be to write down the recursive algorithm to compute $g(n)$, and apply memoization so you don't compute $g(i)$ more than once. In other words, when you compute $g(i)$, you store it in a hash table that maps $i \mapsto g(i)$; if you need to know $g(i)$ again in the future, you can look it up in the hash table.

This does require factoring $n$, but there are efficient algorithms for factoring $n$ when $n\le 10^9$.

You might also look up the sequence $g(1),g(2),g(3),g(4),g(5),\ldots$ in the On-Line Encyclopedia of Integer Sequences. If you find the sequence in their encyclopedia, sometimes they will provide additional helpful information (e.g., efficient algorithms for computing the sequence). That admittedly might take the fun out of things, though.

# Answer
> 0 votes
Here's a hint to get you started. Apply standard dynamic programming algorithms for enumerating the set of partitions of an integer, and add some logic to check which of those allows for unique change-making by iteratively checking all sums, making change, and verifying uniqueness.

In a bit more detail: Suppose you have a multiset $S$. Given a number $i$ with $1 \le i \le n$, how could you identify a submultiset of $S$ that sums to $i$? How could you check whether that submultiset is unique? Try to adapt standard dynamic programming techniques for making change. (See also this question.)

Given a multiset $S$, how could you check whether it satisfies the second condition, i.e., whether every number from 1 to $n$ can be uniquely expressed as a sum of a submultiset of $S$ (the unique change-making condition)? This should be pretty easy, if you solved the previous one.

let $P(n)$ denote the list of multisets that satisfy both of your conditions. If you knew $P(1), P(2), \dots, P(n)$, how could you use that information to construct $P(n+1)$? Here you might want to adapt standard dynamic programming techniques for enumerating the partitions of an integer.

---

Here's an approach that will probably be better.

Suppose $S$ is a multiset that satisfies both of your conditions (for $n$). How can we extend it to get a multiset $T$ that has one element more? In other words, how can we identify all the ways to add one more element to $S$, to get a new multiset $T$ that satisfies both of your conditions (for some $n'$)?

Answer: if $x$ can be expressed as a sum of some of the elements of $S$, then there's no point in adding it to $S$: that would cause $T$ to violate the uniqueness condition. So, we can enumerate all integers $x$ that *cannot* be expressed as a sum of some of the elements of $S$; each one is something that could potentially be added to $S$ to get a new multiset $T$ that will satisfy both conditions (for some other $n$).

Moreover, it is possible to enumerate which integers can be expressed as a sum of some of the elements of $S$, and which cannot, using dynamic programming. You build a two-dimensional array $A\[1\ldots |S|,1 \ldots n\]$ of booleans, where $A\[i,j\]$ is true if there is a way to express the integer $j$ as a sum of some of the first $i$ elements of $S$ (only the first $i$ elements of $S$ are eligible to be used; where $S$ has been sorted, so $S=\\{s\_1,s\_2,\dots,s\_k\\}$ and $s\_1\le s\_2 \le \cdots \le s\_k$). Note that $A\[i,j\]$ can be computing using the values of $A\[1\ldots i-1, 1\ldots j-1\]$: in particular, $A\[i,j\] = A\[i-1,j\] \lor A\[i-1,j-s\_i\]$ if $j\>s\_i$, or $A\[i,j\]=A\[i-1,j\]$ otherwise. This enables us to identify all numbers that are candidates to be added to $S$.

Next, for each candidate extension $T$ of $S$ (obtained by adding one element to $S$), we want to check whether $T$ satisfies both conditions. Let $n$ denote the sum of elements of $S$, and $n'$ the sum of elements of $T$. We need to check whether every integer in the range $n+1,n+2,\ldots,n'$ can be expressed as a sum of some of the elements of $T$. This too can be solved using dynamic programming, using standard algorithms for change-making. (In fact, if you still have the array $A$ mentioned above you can easily extend it a little bit to solve this problem: we make it an array $A\[1\ldots |T|, 1 \ldots n'\]$, continue to fill in all of the additional entries, and make sure that $A\[|T|,n+1\], A\[|T|,n+2\], \ldots, A\[|T|,n'\]$ are all true.) So, now we can enumerate all multisets $T$ that extend $S$ by a single element and that satisfy both conditions.

This immediately suggests an algorithm to enumerate all multisets $S$ that satisfy your condition, for all $n$ up to some bound, say $n\le 20$. We'll have an array $P\[1\ldots 20\]$, where $P\[5\]$ stores all multisets $S$ that sum to 5, and generally, $P\[n\]$ stores the set of all multisets $S$ that sum to $n$.

Next, we can fill in $P\[n\]$ iteratively. Start by setting $P\[1\]$ to contain just the one multiset $\\{1\\}$. Next, for each $n$ (counting up from 1 to 20), for each $S \in P\[n\]$, enumerate all possible extensions $T$ of $S$ (using the techniques above), let $n'$ denote the sum of the elements of $T$, and insert $T$ into $P\[n'\]$ if it isn't already present and if $n' \le 20$.

This should be pretty doable. Good luck! Have fun! Working through the details will be a good learning-exercise in dynamic programming.

---
Tags: algorithms, integers
---


# Question
Title: Average Time Complexity of Two Nested Loops
Recently I have had this question in one of my interviews.

You have 1 Million sorted integer, you have a value of $x$, compare each pair in this array and if the addition of two pair is less or equal to $x$ then increment the paircounter.

I have implemented this solution in C++ however I will write pseudocode here(I am sorry I am not very good at pseudo-code)

```
Initialise ARR_SIZE to 1000000

Initialise index_i to 0

Initialise pairCount to 0

Initialise x to 54321

while index_i is less than ARR_SIZE

  Initialise index_j to index_i+1

    while index_j is less than ARR_SIZE

      if array[index_i]+array[index_j] is less or equal to x

        Increment pairCount

      increment index_j

    endof while

    increment index_x

endof while

```

At first I said it is $O(n \log n)$ but then with the hint the second loop itself average complexity is O(n/2) so overall I said it would be $O(n\cdot n/2)$ but in Big $O$ notation it would be $O(n)$ because $n/2$ is a constant(although I was not too sure). So what is the average complexity of this overall algorithm?

PS: I know that I could have decreased the complexity by adding an extra else, index\_j = ARR\_SIZE, which would be $O(N)$ complexity, but I couldn't think of it during the interview.

# Answer
**How to solve it in O(N)**

Let's take an example sequence of numbers:

`1 3 4 6 7 9`

Assume we want the number of pairs (A,B) where A + B \<= 12.

First, let's compare the 1st (*low* element) and the Nth element (*high* element). 9 + 1 \<= 12. So that's one pair. But, as our list is sorted, 9 is the biggest number, if (9, 1) \<= 12, for any other number X in the list, (X, 1) \<= 12! Meaning, we can just add 6-1 (high index - low index) to the count, we don't need to test those numbers separately. Those are pairs (9,1), (7,1) ... (3,1).

Now we increase our *low* index to 2, we continue to 3. 9 + 3 \<= 12 still, so we add 6-2 to the count. We already added (3,1) in the previous step so this is fine. This adds pairs (9,3), (7,3), (6,3), (4,3).

Again we increase the low index. 9 + 4 \> 12. When this happens, we decrease the high index and add nothing to the count.

Now low index is 3 and high index is N-1. 7 + 4 \<= 12. Adding 5-3... And so on.

If it is unclear why I add `high index - low index` every time: take for example the 7 + 4 step. I know that, because I am at high = 7, I had to skip 9 because it was too large. So I don't want to add the pair involving 9. I also know that because I am at low = 4, I already counted the pairs involving 1 and 3 in the previous steps. So I need to add pairs (7,4) and (6,4) in this step.

```
int count = 0;
for (int low = 0, high = list.Count - 1; high >= 1 && low != high; )
{
    if (list[high] + list[low] <= x)
    {
        count += high - low;
        low++;
    }
    else
    {
        high--;
    }
}

```

**Regarding constants and complexity**

Judging by your comment, you are confused about what is ignored and why. First, `n/2` is not a constant because it depends on `n`. As `n` grows, `n/2` grows, so it is clearly not constant. The constant that is ignored in `n*n/2` is `1/2`, and what remains is `n*n`.

So the complexity is **N^2**. The actual number of inner loop executions is **N^2/2**, but this is still **O(N^2)**. The fact you brought up in your comment that the inner loop will run 50 times when 10^2 would indicate 100 times is irrelevant, here's why:

Constants are not meaningful unless they are extremely large (a `2^32` constant because your algorithm tests every 32 bit integer) or you calculate the average case cycle count on a reference architecture.

Otherwise, actual speed depends on the language used, on how many instructions each operation actually performs, prediction, caching, pipelining, etc and it is difficult to compare the constants of 2 different algorithms, just outright counting syntactic constructs is very misguided.

`2X` operations may run faster than `X` operations if what is being done, how and in which order is different. So until you dig a bit deeper and look into the things I mentioned above, counting operations in a high level language is **pure wishful thinking**. It is a sign of a questionable CS teaching in my opinion because it teaches a nonsense model of code execution, instead of using a valid one, but on a simple reference architecture (like Knuth does), if you insist on counting operations.

Consider these two pieces of code:

```
for (int j = 0; j < N - 1; j++)
    for (int i = j + 1; i < N; i++)
        r += A[i][j];

```

And:

```
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

```

The first example has `N^2 / 2` inner loop repetitions. The second example has `N^2` inner loop repetitions. The inner loop body is the same. But the second one is actually much faster on a standard computer (in fact, a smart compiler with certain settings might rewrite your code if you write the first one - so if you test this, turn off optimization)! This is because the second one has much better memory access locality - it accesses the memory locations in order, while the first one jumps around. This causes a much bigger difference in speed than running the loop twice as many times does. And this is **just one of many things** which affect run speed and are not immediately visible in the code.

Second example, two pieces of code:

```
for (int i = 0; i < N - 1; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        int a = A[i][j] * 3;
        a += 5;
        r += a;
    }
}

```

And:

```
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

```

Can you tell me which one has a bigger "constant"? Again, the first inner loop runs 1/2 as many times as the second one. But the first one has 3 lines of code inside the inner loop, while the second one has just one. On my machine, the first one is faster. By what factor? I have no idea (I could measure it, but I can't tell you by looking at the code). If you decide on a constant A for the first and B for the second program by looking at the code, A/B will probably not be anything like the ratio of actual execution times, making the constants meaningless.

So the 1/2 constant is meaningless. Whether a program runs twice faster than some other program depends on so many things that it is not productive to account for small constants *on such a superficial level*.

By the way, you have a bug in your program. The outer loop condition needs to be `less than ARR_SIZE - 1` or you are setting `index_j` to `ARR_SIZE` in the last outer iteration, and as your indices are 0-based you are reading from beyond the end of your buffer.
> 2 votes

# Answer
To add to @svinja's solution, instead of traversing the whole list of a million numbers, do the following -

```
L : List of million integers
S : @svinja's algorithm
Assuming indices start from 1 in L
int positionOfX = binarySearch(L, x), where positionOfX = -(insertionPoint) in case x does not exist in L

```

Apply S to L but traverse from 1 to i where i is at max abs(positionOfX/2) + 1.
> 0 votes

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


# Question
Title: Classification of job shop scheduling problems
I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory.

* The factory has several types of machines (say, `locksmith, miller, welding`)
* There are few machines of each type. (say, `3 locksmiths, 2 millers, 3 welders`)
* There are several types of operations (some machines do more than one operation on the job, say, `locksmith does soldering and assembling`).
* The jobs on the machines have different times, all known beforehand.
* The jobs have dependencies on jobs done before (say, `a product's made of 10 screws and 4 subparts, each of which needs 4 screws`).

From what I searched, this looks sort of like a Flow Shop problem. The difference is in the dependencies and in the same machine doing different operations with different times on a job.

---

## My main question is:

**Is there some kind of a classification of these problems?** A summary telling the differences?

For example, I don't understand much of how do these differ: Open Shop, Job Shop, Flow Shop, Permutation Flow Shop. And whether or not I missed something similar that could fit better to my problem.

---

As a side question, what approach do you think could help me best with the unusual requirements I've posted above? I'm writing my current approach below.

So far I've been able to work with the tree of dependencies without regard to the makespan times: just making a plan - a list of IDs, really - of what comes after what, from looking at the tree of what's been done so far and what are the leaves (nodes having done all their dependencies).

This allows for fast creation of meaningful individuals in the Genetic Algorithm population, but there seems to be no computationally cheap way to learn the individual's makespan time (which I have as the fitness function).

For that I have to create a calendar, or Gantt chart, if you will, to which I put the operations on the jobs in the earliest place possible, in the machine queue that's free at that moment, etc. The whole plan has to materialize and that seems the most costly computation of the whole problem.

# Answer
In searching around for an online presence for one of the classics in this field (Coffman, Denning: Operating Systems Theory, Prentice Hall, 1983) I came upon what looks like a comprehensive textbook with a Google books preview Pinedo: Scheduling: Theory, Algorithms, and Systems, Springer 2008. The author's homepage also has pages devoted to each of his books. It has chapters for multiprocessor scheduling, open shop scheduling, flow shop scheduling and job shop scheduling.

The *flow shop* problem has $n$ jobs with $m$ machines. Each job needs to visit machines in the exact order $1,2,\ldots,m$. There are $nm$ parameters $d\_{ij}$, which is the amount of time job $i$ demands on machine $j$. There is no constraint on the order in which machines service jobs. (The constraint is on the order in which jobs need machines.)

The *permutation flow shop* problem seems to add the constraint that every machine must service the jobs in the same order. So the goal is to permute the jobs to minimize the makespan of pipelining each job through the machines in order.

The *open shop* problem completely relaxes the ordering constraints. Each job demands time on each machine, but in no particular order. (And, of course, the amount of time demanded by job $i$ on machine $j$ can be 0.)

The flow-shop problem and open-shop problems are special cases of the more general job shop problem with precedence constraints: We are given a set of jobs $J=\\{J\_1,\ldots,J\_n\\}$ and a set of resources $R=\\{R\_1,\ldots,R\_m\\}$. Each job $J\_i$ consists of a set of operations $O^i=\\{O\_1^i,\ldots,O\_p^i\\}$. Each operation $O\_k^i$ requires a set of resources $R\_k^i \subseteq R$ for a time $t\_k^i$, and for each job, $J\_i$ there is a set of *precedence constraints* (i.e., a partial order or directed graph) on the operations, $O\_k^i \xrightarrow\[\mathrm{before}\]{} O\_l^i$, stating that operation $O\_k^i$ needs to finish before $O\_l^i$ starts.

Your problem is a job-shop problem with an additional generalization that there are classes of identical resources ("3 locksmiths") and the operations can use any resource in the class. This brings in an aspect of the multiprocessor scheduling problem.

N.B., I believe that I've used the terminology that is used in the books by Coffman and Denning, and by Pinedo. The wikipedia pages are an utter disaster. The wikipedia page on job shop scheduling gives a definition of the open-shop problem that contradicts the wikipedia page on open shop scheduling. The wikipedia page on the flow shop problem is incomprehensible. And wikipedia is confused about the difference between *multiprocessor scheduling*, which involves $m$ *interchangeable* resources, and job-shop scheduling. For example, the wikipedia page on the Coffman-Graham list scheduling algorithm calls it a solution to the job-shop scheduling problem, although Coffman and Graham use the term "multiprocessor", not job-shop in the titles of their papers. (And note that the author of the wikipedia page on multiprocessor scheduling seems unaware of the original variant with precedence constraints.)
> 10 votes

---
Tags: optimization, scheduling, heuristics, genetic-algorithms
---


# Question
Title: Data structure for storing edges of a graph
I'm currently working on my masters thesis, and it's about clustering on graphs. I'm working with an idea using ants to solve the problem. I'm currently working on the implementation and am wondering exactly how well to represent the edges of the graph.

Each edge is augmented with certain information such as its pheromone value and the number of times an ant has visited that edge. I'll be working with undirected graphs, which can be end up being pretty huge (over a million vertices) and I was wondering what is the most efficient way for me to store the edges and look them up? I was thinking of sticking to a convention and store endpoints according to the one which has a lower vertex id for $v\_1$ and the higher one for $v\_2$ ($v\_1$ and $v\_2$ are the endpoints of the edge in the data structure). But I'm wondering how would I perform a look up in this case?

There is a mapping I came up with from the adjacency matrix to the edge array, but that works only if the underlying graph is a complete graph. So I came here for some suggestions as to how I should proceed because I need my lookup to be efficient while at the same time I don't want to blow up the storage space for the edges as the graphs will be huge.

# Answer
If your graph is sparse then you should store it using adjacency "lists", though you probably want something more efficient than a list (or perhaps you don't, depending on usage). It's simplest if you store each edge at both endpoints. This can be implemented in many ways, for example you can store all data in some big array, and store only pointers in the adjacency "lists".
> 5 votes

---
Tags: graphs, data-structures, evolutionary-computing
---


# Question
Title: How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $
I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where $d\>1$. The question is how to compute the level set $A=\left\\{ \theta:f\left(\theta\right)\geq a\right\\} $. I am a statistician knowing very few things about computer science. I would appreciate very much if anyone could suggest some reference, methods and/or alogirthms.

In my problem, $f\left(\theta\right)=\sum\_{i=1}^{N}\log g\left(\mathbf{z}\_{i};\theta\right)$, where $g\left(\mathbf{z}\_{i};\theta\right)$ is a probability density function of $\mathbf{z}\_{i}$ parameterized by a vector of parameters $\theta$. $\mathbf{z}\_1,\ldots, \mathbf{z}\_N$ are observed samples. For example, $g\left(\mathbf{z}\_{i};\theta\right)$ is the density function of a normal distribution with variance $1$ $$ g\left(\mathbf{z}\_{i};\theta\right)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{\left(y\_{i}-\mathbf{x}\_{i}'\theta\right)^{2}}{2}\right). $$ Here $\mathbf{z}\_{i}=\left(y\_{i},\mathbf{x}\_{i}\right)'$.

# Answer
We can compute $$ f(\theta) = -N\log (2\pi)-\frac{1}{2}\sum\_{i=1}^N (\langle x\_i,\theta \rangle -y\_i)^2. $$ Expanding this out, we get that $f(\theta)$ is some quadratic form: $$ f(\theta) = \theta' A \theta + v'\theta + C, $$ where $A$ is symmetric. The next step is to get rid of the linear term. Let $\theta = \psi + \epsilon$. Then $$ \theta' A \theta + \langle v,\theta \rangle + C = \psi' A \psi + (2\epsilon' A + v') \psi + (\epsilon' A \epsilon + v'\epsilon + C). $$ So choosing $\epsilon' = -v' A^{-1}/2$ (assuming $A$ is invertible), we get $$ f(\psi + \epsilon) = \psi' A \psi + C'. $$ The theory of quadratic forms tells us that if $A$ is invertible then we can write $A = P'DP$, where $D$ is a diagonal matrix with $\pm 1$ on the diagonal and $P$ is invertible. If $\psi = P \chi$ then $$ f(P^{-1} \chi + \epsilon) = \chi' D \chi + C' = \sum\_{i=1}^k \delta\_i \chi\_i^2 + C', $$ where $\delta\_i \in \\{\pm 1\\}$. Suppose for example that the first $k\_+$ are $+1$ and the rest $k\_- = k - k\_+$ are $-1$, and write $\chi = \[\chi\_+\\;\chi\_-\]$. Then $$ f(P^{-1} \chi + \epsilon) = \\|\chi\_+\\|^2 - \\|\chi\_-\\|^2 + C'. $$ If $k\_+ = 0$ or $k\_- = 0$ then the level sets are spheres or cospheres, up to an affine transformation of course. Otherwise it gets more complicated.

In your case, however, it is clear from the function $f$ itself then the quadratic form $A$ is negative semidefinite, probably in fact negative definite. In other words, $k\_+ = 0$. So the sets you're after are affine transformations of cospheres. In other words, they are "outsides" of ellipsoids.

The only non-trivial step is finding the matrix $P$. Since your matrix is negative definite, you can use Cholesky decomposition.
> 5 votes

---
Tags: algorithms, probability-theory, mathematical-analysis, real-numbers
---


# Question
Title: Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?
A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. The number of distinct clique trees can be exponential in the number of vertices in a chordal graph.

The *reduced clique graph* $C\_r(G)$ is the union of all clique trees of $G$. That is, it has all the same vertices, and all possible edges. What is the complexity of computing $C\_r(G)$ for a given $G$?

I think I once saw a presentation claiming $C\_r(G)$ can be computed in $O(m+n)$ time without proof. This would mean it is as easy as computing a clique tree of $G$. Is there a reference that confirms this, or gives a slower algorithm for computing it?

# Answer
> 2 votes
The complexity is O(nm)... from G compute the maximal cliques and make them vertices in your graph H (initially with no edges)... then compute all minimal separators and order them by size... pick the largest separator S and make any two cliques C,C' adjacent in H (connect them by an edge with label S) if C,C' both contain S and are in different connected components of H (initially this is of course always true, but may not be later)... then pick next largest separator and do the same... repeat until all separators are processed... the resulting graph H is the reduced clique graph of G... computing maximal cliques and minimal separators takes O(n+m)... there are O(n) cliques and O(n) separators... the rest of the construction is O(nm) as processing each separator can take O(m) time... ... this cannot be improved below O(n^2) unless you can solve the following problem: given a graph G find two vertices u,v such that N(u) contains N(v)... the latter is not known to have O(n+m) solution... ... it is therefore unlikely that a O(n+m) algorithm for computing reduced clique graphs is possible...

see Section 5 in M. Habib, J. Stacho: Polynomial-time algorithm for the leafage of chordal graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757/2009, pp. 290-300. (http://www.cs.toronto.edu/~stacho/public/leafage-esa1.pdf)

---
Tags: algorithms, graphs, reference-request
---


# Question
Title: Checking Feasibility of Linear Program in Polynomial Time
Given a linear system of the form:

$$\begin{array}{c} x\_r = a \quad x\_j = b \\ c\_1x\_1 + c\_2x\_2 + \ldots + c\_nx\_n = N \\ x\_1+x\_2 + x\_3 + \ldots + x\_n = k\\ 0 \le a,b,x\_1,x\_2,x\_3...x\_n \le 1\\ k \ge 0 \end{array}$$

How quickly can the feasibility of the system be checked? To clarify: $x\_r,x\_j$ are members of $x\_1,x\_2...x\_n$. Would it be $O(n^{3.5})$ since I believe that is the general complexity for running a linear program or would it be less? Can one use gaussian elimination to quickly reduce the first 4 equations in $O(n^3)$ and after that systematically move through the equations starting from the terms with largest coefficient and moving to terms with smallest coefficient assigning values that bring the equations as close to satisfactory as possible?

Additional info:

I am assuming that the number of variables scales linearly. $n \ne N$ (I think that was clear though).

# Answer
> 6 votes
**Restating the problem.** As far as I can tell, your system is equivalent to the following:

$$c\_1 x\_1 + \dots + c\_n x\_n = N$$

subject to the constraints

$$0 \le x\_1, \dots, x\_n \le 1.$$

**Solving this problem.** This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are polynomial-time algorithms for linear programming.

However, there's a better solution. We can directly solve this problem by inspection, without needing a linear programming solver.

Suppose without loss of generality that $c\_1,\dots,c\_j$ are positive and $c\_{j+1},\dots,c\_n$ are zero or negative. (You can re-order the variables to put things into this standard form.)

Then it follows that $c\_1 x\_1 + \dots + c\_n x\_n \le c\_1 + \dots + c\_j$. So, if $c\_1 + \dots + c\_j \< N$, then this problem has no feasible solution. On the other hand, if $N \le c\_1 + \dots + c\_j$, then it is easy to demonstrate that this problem does have a solution: simply let $x\_1 = \cdots = x\_j = N/(c\_1 + \dots + c\_j)$ and let $x\_{j+1} = \cdots = x\_n = 0$. These $x\_i$'s will all fall in the desired range.

Thus, feasibility can be checked in $O(n)$ time (in the RAM model, where basic operations take $O(1)$ time).

---

**Details.** Why is it fair game to reduce the problem to the form given above? How did I get the simpler form above?

Well, first off, I removed the variables $a,b$ from the linear program. No matter what values you assign to the $x$'s, you'll always be able to assign a value to $a,b$ derived from the $x$'s that satisfies the equations that mention $a,b$.

Similarly, I removed the equation $k=\dots$ and the variable, since no matter what value we assign to the other variables, we can simply set $k=x\_1+\dots+x\_n$ and get a value that will satisfy this equation; it will also satisfy $k\ge 0$, since all the $x\_i$'s are required to be $\ge 0$. That leaves me with the problem shown at the top of my answer.

---
Tags: complexity-theory, time-complexity, computational-geometry, linear-programming, linear-algebra
---


# Question
Title: Computing 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time
I've constructed an algorithm that solves the 3SUM problem in $O(n\lg n) + \frac{n^2}{4}$ time. I'm new to algorithms and was wondering how good is my running time? Googling didn't help. thanks..

# Answer
> 4 votes
There are known algorithms that take strictly less than $O(n^2)$ time (i.e., they run in $o(n^2)$ time), under certain theoretical computational models. See, e.g.,

However, it is not clear to me whether this leads to a practical improvement in real implementations.

Did you do a literature search for work on the 3SUM problem? The above paper immediately comes up as soon as you search for "3SUM" on Google Scholar. On this site, we expect you to do your own research first before asking here, and to show what you've tried in your question. Please make sure to read the help center to learn more about how this site works. You might want to do a literature search, including reading the relevant references cited in the paper above, then editing your question to reflect this research -- or adding an answer to answer your own question.

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


# Question
Title: Closed-form Expression of the Expected value of the Cost of D&C Algorithm?
Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$ and $q$ , respectively. Each bit in the string is independent of any other bit.

There is an algorithm (divide and conquer) which finds the location of 1’s in a given binary-string, in Q # of steps (cost).

I am looking for some close-form solution of the expected # of steps,$E\[Q\]$, with given probabilities $p$ and $q$ for a string of length $N$.

For instance, for $N=4$ the cost ,${{Q}\_{i}}$, for each possible word is:
\[\begin{matrix} {{B}\_{i}} & {{Q}\_{i}} & {{P}\_{i}} \\ 0000 & 1 & {{p}^{4}} \\ 0001 & 5 & {{p}^{3}}q \\ 0010 & 5 & {{p}^{3}}q \\ 0011 & 5 & {{p}^{2}}{{q}^{2}} \\ 0100 & 5 & {{p}^{3}}q \\ 0101 & 7 & {{p}^{2}}{{q}^{2}} \\ 0110 & 7 & {{p}^{2}}{{q}^{2}} \\ 0111 & 7 & p{{q}^{3}} \\ 1000 & 5 & {{p}^{3}}q \\ 1001 & 7 & {{p}^{2}}{{q}^{2}} \\ 1010 & 7 & {{p}^{2}}{{q}^{2}} \\ 1011 & 7 & p{{q}^{3}} \\ 1100 & 5 & {{p}^{2}}{{q}^{2}} \\ 1101 & 7 & p{{q}^{3}} \\ 1110 & 7 & p{{q}^{3}} \\ 1111 & 7 & {{q}^{4}} \\ \end{matrix}\] From the discrete probability theory, we can evaluate the expected cost of the above case ,$N=4$,as follow $\begin{align} & \therefore E\[Q\]=\sum\limits\_{i=0}^{{{2}^{N}}-1}{{{Q}\_{i}}({{p}^{N-i}}}{{q}^{i}}) \\ & \Rightarrow E\[Q\]=\sum\limits\_{i=0}^{15}{{{Q}\_{i}}({{p}^{N-i}}}{{q}^{i}}) \\ & \Rightarrow E\[Q\]={{p}^{4}}+4\times 5\times {{p}^{3}}q+2\times 5\times {{p}^{2}}{{q}^{2}}+4\times 7\times {{p}^{2}}{{q}^{2}}+4\times 7\times p{{q}^{3}}+1\times 7\times {{q}^{4}} \\ & \Rightarrow E\[Q\]={{p}^{4}}+20{{p}^{3}}q+10{{p}^{2}}{{q}^{2}}+28{{p}^{2}}{{q}^{2}}+28p{{q}^{3}}+7{{q}^{4}} \\ \end{align}$

However, for very large values of N, say 1024, it is computationally not possible to evaluate the cost of each possible binary string (i-e ${{2}^{1024}}=\text{1}\text{.79}\times \text{1}{{\text{0}}^{308}}$ binary words). So, this is the problem I am stuck in.

Is it possible to deduce some analytical/ close-form expression for evaluating the expected value of the cost of this algorithm for a given length N and probabilities p and q (instead of brute-force method defined above)?

I will be very thankful, if someone could help in this regard.

ADDITIONAL INFORMATION:

Divide & Conquer Algorithm: Lets take 0000 0001, for instance:

1. First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.
2. Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?
3. Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.
4. This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

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

Efficient Way for evaluating the cost of Above algorithm: (courtesy to Yuval Filmus)

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

For example, suppose $x=0101$. Then the sequence is $$ 11,1, $$ and so $N = 3$ and the cost is $7$.

# Answer
Expectation is additive, so your expectation equals $$ E := 2E\[w(O(x))\] + 2E\[w(O(O(x)))\] + \cdots + 2E\[w(O(\cdots(x)\cdots))\] + 1, $$ where $w(\cdot)$ is Hamming weight. Let's calculate $E\[w(O(x))\]$, again using the fact that expectation is additive. The probability that the $i$th bit of $O(x)$ is $1$ is exactly $1-p^2$, and there are $N/2$ of them, therefore $E\[w(O(x))\] = (N/2)(1-p^2)$. Similarly, the probability that the $i$th bit of $O(O(x))$ is $1$ is exactly $1-p^4$, and there are $N/4$ of them, and so $E\[w(O(O(x))\] = (N/4)(1-p^4)$. If $N = 2^n$, then we get $$ E = 2^n (1-p^2) + 2^{n-1}(1-p^4) + \cdots + 2(1-p^{2^n}) + 1.$$ We can simplify this slightly by summing the geometric series: $$ E = 2^{n+1}-1 - 2^n p^2 - 2^{n-1} p^4 - \cdots - 2p^{2^n}. $$
> 2 votes

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


# Question
Title: I'm lookin for a method to construct a particular grammar?
I'm looking for an algorithm to construct a grammar which, given a set of words which can have multiple identical symbols, represents a compressed version of this set, that is, I can generate only the words of the set but the grammar will take less memory than the set himself.

Besides, I'm looking for an algorithm which can update the grammar when I want to remove a word of the set.

What type of algorithm is able to do that ?

I give a concrete example:

Consider a string S="abcdefghij", and then consider the finite set of words "cdhij", acdef", "fghi", "bcfgij", "defi".

I would like to construct a grammar which generates only this set of words (words which can be viewed as concatenation of various substrings of any length from the original string S).

Finally I would like to remove a word in the set and update subsequently the grammar.

Thank you.

# Answer
it is not clear what you mean by "words which have multiple identical symbols". it sounds like you mean certain symbols are interchangeable. in that case, just replace all cases of an interchangeable symbol with a single representative symbol.

as to the more general question, there is an area of CS not-so-widely studied, called grammar based codes which is, roughly, focused on the idea of creating compressions of strings based on grammar expansions. in this way classic compression algorithms such as eg Lempel Ziv can be regarded as special cases of grammar compressions.

your problem is not so well defined unless you specify the type of grammar also, eg say CFG. if the grammar is generated by a recursive machine, then this problem is actually similar or almost identical to finding the Kolmogorov complexity of a string, which is undecidable in general.
> 2 votes

# Answer
The keyword is "CFG induction": given several examples of words from a CFG, find the smallest/simplest context-free grammar (CFG) that generates those words. If you do a literature search with that phrase, you'll find prior work on this problem. It is a highly non-trivial problem, but you should be able to find some algorithms, e.g., the TBL algorithm. You might also find papers under the phrase "learning a CFG".

Another approach is to use regular languages (e.g., finite-state automata). There are known algorithms for learning regular languages, i.e., given one or more words from a regular language, find a small finite-state machine that accepts those words. See, e.g., the seminal algorithm by Angluin and this survey on the hardness of finding the absolutely smallest possible finite-state machine. For more, look for papers on "DFA learning" and related topics. You might also be interested in MERLIN and this book on learning grammars.
> 0 votes

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


# Question
Title: Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$?
The problem is from CLRS 9.3-1:

> In the algorithm `SELECT`, the input elements are divided into groups of $5$. Argue that `SELECT` does not run in linear time if groups of $3$ are used.

If we do the "divide by $3$" technique, we will come up with this recurrence --

$$T(n) = \begin{cases} \Theta(1) & \text{if $n \le K$} \\ T(\lceil n/3 \rceil)+T(2n/3+4) + O(n) & \text{if $n \ge K$} \end{cases}$$

I have solved by substituting $T(n) \le cn$ and $O(n) = an$ --

$$\begin{aligned} T(n) & \le \lceil n/3 \rceil + c(2n/3 + 4) + an \\ & \le cn/3 + c + 2cn/3 + 4c + an \\ & = cn + 5c + an \\ & = (c+a)n + 5c \\ & = c\_1n + c\_2 \le c\_1n \approx O(n) \end{aligned}$$

But the solution says it should be $\Omega(n \lg n)$. I understand that substitution like $cn \lg n$ could give $\Omega(n \lg n)$ bound, but what is wrong with $O(n)$ formulation above?

# Answer
You started with the induction hypothesis $T(k) \le ck/3$ for all $k\<n$, but you didn't prove that $T(n)\le cn$. You concluded that $T(n) \le c\_1 n$, for a **different** constant $c\_1 \ne c$. For the induction proof to work, you have to use the **same** constant in the induction hypothesis and the conclusion.
> 7 votes

---
Tags: algorithm-analysis, recurrence-relation, search-algorithms
---


# Question
Title: State machine with knowledge of prior states?
I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.

Below is an example graph descibring the process. The essence is: If both State Q1 and State Q3 recieve an input of one, after State 3, transition to State Q4, otherwise transition to State Q5.

I understand that it would be possible to model this using a finite-state machine where we duplicate any states between those that we are interested in. The example below demonstrates this with States Q2a and Q2b corresponding to the differences in input at state Q1

However, as the number of conditions and the gaps between them grows (both of which are possible in the process I'm looking at), the number of states grows exponentially.

The question is, what other computational models could be used to describe a process where an arbitrary number of inputs could be used to control transition between states?

# Answer
In digital design we would call the thing you are looking for an *algorithmic state machine*. In compiler design we would call it a *control flow graph*. The idea in either case is that you divide the state problem into two parts, one part represents the *control state*, the other part represents the *data path*. You label the states with how you want the data path to be modified, and the data path has some boolean outputs that you use to determine which way the control state should change.

Formally, you are describing a *Moore machine* where each state describes a set of control signals that will be sent to tell the data path how to modify itself, and the data-path in turn has a small set of boolean outputs that are used as the input language to the control state machine.

Your original problem would then have a control state, `Q`, and two variables, `v1` and `v2` and the graph would look something like:

```
       q1: v1 <- some_function(...)
                |
                v
       q2: something else happens
                |
                v
    q3: v3 <- some_other_function(...)
        test (v1==1 && v3==1)?
       /                 \
       | true             | false
       v                  v
q4: something    q5: something else
       \                  /
        \                /
         v              v
           q6: whatever

```
> 2 votes

# Answer
In Petri nets, state is distributed; basically, there is no distinction between state transitions and messages. This allows a much more compact representation of certain types of systems, which may or may not include the sorts of systems you are trying to model. They may be particularly useful if your inputs and output signals cannot queue up.
> 1 votes

---
Tags: graphs, automata, network-flow
---


# Question
Title: $\mathbf{NC}$ is closed under logspace reductions
I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the $\mathsf{PATH}$ problem (decide whether a graph $G$ has a path from a given node $s$ to another given node $t$) which is complete for $\mathbf{NL}$ is also contained in $\mathbf{NC}$ (this is easy). The question then also makes a remark that this implies that $\mathbf{NL} \subseteq \mathbf{NC}$ which is not obvious to me.

I think in order to show this, one has to show that $\mathbf{NC}$ is closed under logspace reductions, i.e

$$(1): B \in \mathbf{NC} \hbox{ and } A \le\_l B \Longrightarrow A \in \mathbf{NC}$$

where $\le\_l$ is the logspace reduction defined as

$$A \le\_l B :\Longleftrightarrow (\exists M \hbox{ TM}, \forall x)\[x \in A \Longleftrightarrow M(x) \in B\]$$

($M$ is a TM which runs in logarithmic space).

I would appreciate if someone could give a tip for proving the statement $(1)$.

# Answer
> 6 votes
Given any language $L$ in NL decided by some machine $T$, you can decide whether $x \in L$ by considering the configuration graph of $T$ when run on $x$. This is why PATH is NL-complete. Given any length $n$ of the input, the configuration graph is a fixed polynomial-size graph which doesn't depend on $x$. Only the starting vertex depends on $x$. We can arrange that the starting configuration corresponding to an input $x$ is configuration (vertex) number $x$. This implies that $L$ is in NC.

If we are careful we can do better and show that $L$ is in fact in uniform NC (under various definitions of uniform). The idea now is that given two configurations $\sigma\_1,\sigma\_2$, it is easy to decide whether $\sigma\_1$ can reach $\sigma\_2$ in one step. According to the complexity zoo, this way we can show that PATH is NL-complete under first order reductions (uniform AC0 reductions). Since uniform NC is closed under first order reductions, this implies that NL is in uniform NC.

---
Tags: complexity-theory, reductions, closure-properties, complexity-classes, parallel-computing
---


# Question
Title: If a parser can parse a non-deterministic grammar, is the parser non-deterministic?
I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, `S → 0S0 | 1S1 | ε`, which checks for an even-length palindrome, is a non-deterministic grammar. My parser generator can handle this grammar. Does that mean my parser is non-deterministic?

To be honest, I'm not even sure that it's proper to try to classify it like this. It doesn't really match the description of a pushdown automata, since it passes data up and down through the stack (parameters, passed by reference, which may be modified). If anyone would be interested in taking a closer look at it, I'd be most grateful. It handles left recursion and ambiguous grammars in (I believe) polynomial time and space. https://github.com/coder0xff/parlex

# Answer
No, it doesn't mean that. A non-deterministic algorithm is one that uses non-determinism. You're not using non-determinism; your algorithm is completely deterministic.

Here's what's tripped you up. You can recognize a non-deterministic grammar using a deterministic algorithm. Similarly, you can recognize whether a word is accepted by a non-deterministic finite automaton (NFA) using a deterministic algorithm (e.g., simply convert the NFA to a DFA, then check whether the DFA accepts the word). So, no, just because the grammar is non-deterministic does not mean that we should call your parsing algorithm non-deterministic.
> 2 votes

---
Tags: formal-grammars, pushdown-automata, parsers
---


title: Universes in dependent type theory

text:
# Question
Title: Universes in dependent type theory
I am reading about dependent types theory in the Homotopy Type Theory online book.

In section 1.3 of the *Type Theory* chapter, it introduces the notion of hierarchy of *Universes*: $\mathcal{U}\_0 : \mathcal{U}\_1 : \mathcal{U}\_2 : \cdots$, where

> every universe $\mathcal{U}\_i$ is an element of the next universe $\mathcal{U}\_{i+1}$. Moreover, we assume that our universes are cumulative, that is that all the elements of the $i^{\mathrm{th}}$ universe are also elements of the $(i+1)^{\mathrm{th}}$ universe.

Yet, when I look at the formation rules for the various types in appendix A, at first glance, if a universe appears above the bar as a premise, the same universe appears below. For instance for the coproduct types formation rule:

$$\dfrac{\Gamma \vdash A : \mathcal{U}\_i \quad \Gamma \vdash B : \mathcal{U}i}{\Gamma \vdash A + B : \mathcal{U}\_i}(+\mbox{-}FORM)$$

So my question is why is a hierarchy necessary? **Under what circumstances do you need to jump from a universe to one higher in the hierarchy?** It is really not obvious to me how given any combination of $A\_m: \mathcal{U}\_i$, you can end up with a type $B$ that is **not** in $\mathcal{U}\_i$. In more details: the formation rules in sections of the appendix A.2.4, A.2.5, A.2.6, A.2.7, A.2.8, A.2.9, A.2.10, A.3.2, either mention $\mathcal{U}\_i$ in the premise and judgement, or just in the judgement.

The book also hints that there is a formal way to assign universes:

> If there is any doubt about whether an argument is correct, the way to check it is to try to assign levels consistently to all universes appearing in it.

**What is the process for assigning levels consistently?**

$\mathcal{U}:\mathcal{U}$ would lead to the Russell paradox. Avoiding the Russell paradox is explicitly mentioned in the book (page 24). It also goes into more details page 54, 55 that is uses “Russell-style universes” rather than “Tarski-style universes”. So at a very high level, I take for granted that the theory wants to avoid the paradox. Unfortunately I don't have the background to make sense of out that directly. What I am after in this question, is really just scratching the surface by getting some examples of things in $\mathcal{U}\_j$ and not in $\mathcal{U}\_i$ for $j \> i$ and may be anything else that give me a feel for how the hierarchies work.

# Answer
> 16 votes
The question under what circumstances we need to jump from a universe to one higher in the hierarchy is a good one. Having the hierarchy and the ability to climb it is important. You need to jump levels when you want to treat a universe as a type or as part of a type. For example to define functions of (non-dependent) type $$ A \rightarrow \mathcal{U}\_i $$ you must show that $A \rightarrow \mathcal{U}\_i$ is in a universe. But that cannot be $\mathcal{U}\_i$ or some smaller universe. So what do we do? To deal with the problem (without using the unsound $\mathcal{U}\_i : \mathcal{U}\_i$), we need to jump up a universe. The rule that enables us to make this jump is $\mathcal{U}$-Intro $$ \frac{\vdash \Gamma : ctx}{\Gamma \vdash \mathcal{U}\_i : \mathcal{U}\_{i+1}}, $$ given in Appendix A.2.3. The very point of the hierarchy of universes is that we can do this. This can be seen as a safe approximation of having universes contain themselves.

# Answer
> 14 votes
I will slightly amend Martin's answer to explain where *cumulativity* comes in (the rule which says that $X : \mathcal{U}\_i$ and $i \leq j$ entail $X : \mathcal{U}\_j$). Suppose we have $A : \mathcal{U}\_{42}$ and we would like to give a type to $A \to \mathcal{U}\_{99}$. The formation rule for $\to$ is this: $$\frac{\Gamma \vdash X : \mathcal{U}\_i \qquad \Gamma \vdash Y : \mathcal{U}\_i}{\Gamma \vdash (X \to Y) : \mathcal{U}\_i}$$ (If $X \to Y$ is a shorthand for $\Pi\_{x : X} Y$ then the above rule could be derived from the formation rule for $\Pi$, but let us not worry about it.) In order to use this rule, both types involved in the formation of the function type must be in the same universe. In our case we have $A$ in $\mathcal{U}\_{42}$ and $\mathcal{U}\_{99}$ in $\mathcal{U}\_{100}$. So we first use cummulativity to deduce that $A : \mathcal{U}\_{100}$ as well, and then proceed to show that $A \to \mathcal{U}\_{99}$ has the type $\mathcal{U}\_{100}$.

We could get rid of cummulativity, but then the rules become more complex. For example, formation of $\to$ would read $$\frac{\Gamma \vdash X : \mathcal{U}\_i \qquad \Gamma \vdash Y : \mathcal{U}\_j}{\Gamma \vdash (X \to Y) : \mathcal{U}\_{\max(i,j)}}$$ or $$\frac{\Gamma \vdash X : \mathcal{U}\_i \qquad \Gamma \vdash Y : \mathcal{U}\_j \qquad i \leq k \qquad j \leq k}{\Gamma \vdash (X \to Y) : \mathcal{U}\_k}$$ In any case, type theory has many subtle variations, and getting them all to play together nicely seems to be a bit of an art.

---
Tags: type-theory, homotopy-type-theory, dependent-types
---


# Question
Title: Complexity of the V-opt heuristic Traveling Salesman algorithm
The paragraph on V-opt heuristic TSP algorithms at this site mentions a very effective algorithm due to Lin-Kernigham-Johnson. That page says:

> For many years Lin–Kernighan–Johnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best known solutions for all other TSPs on which the method had been tried.

Impressive, so what is the complexity of that algorithm? Does the algorithm often work faster than predicted based on theoretical complexity (if yes, how much)? Is that algorithm used most often in software that solves the TSP?

# Answer
According to the original 1973 paper, the Lin-Kernighan algorithm

> ...produces optimum results with high frequency, in running times that grow about as $n^2$.

The iterated Lin-Kernighan variant, proposed by Johnson in 1990, offers an observed improvement to $O(n^{1.25})$; an experimental treatment of this and many other local optimization TSP heuristics can be found here.
> 3 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, traveling-salesman
---


# Question
Title: Reference request: Monads, continuations, and other functional CS concepts
I've been using Clojure for about 18 months. Recently, I've come across terms such as Monads, Continuations, et al which I'd like to learn about.

I could visit Wikipedia and read about these two topics, but I'm looking for a reference which also help me learn about related matters that I don't even know exist. Is there a book on this particular topic (if it even qualifies as one)? Would I pick these things up by learning about type systems or language design in general? Should I just learn Haskell to get exposure?

# Answer
I would focus on learning a functional language in order to learn these. There's no need for it to be Haskell. It could be Scheme or ML, or even Coq or Agda. Frankly, Clojure will probably do. But to me, monads and continuations are only programming tools. They don't let you do any new computations, they just let you do them in a different way. So understanding them outside of the context of a particular style of programming to me doesn't make much sense.

I'd recommend Real World Haskell as an introduction to some of these concepts, particularly in how they can be used in programming. I'm not sure how much it has on continuations. I learned continuations from Essentials of Programming Languages, which I quite liked, but deals with Scheme rather than Haskell, and doesn't do anything monadically.
> 3 votes

# Answer
I agree with @jmite that the best resources on continuations are likely to come from the Scheme community. Here's a brief tutorial that looks very good: Jeremy H Brown, *Advanced Scheme*. The tutorial also discusses Scheme's hygienic macros which might also interest you since Clojure has a similarly powerful macro facility.

For monads I originally tried to learn from reading the Haskell community's research papers and gave up in despair. Eventually I found Simon Peyton Jones: "Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell", in *Engineering theories of software construction*, Hoare, Broy, Steinbruggen, ed., IOS Press, ISBN 1 58603 1724, 2001, pp47-96, which is somewhat better, but still written for an IQ higher than mine.

Finally I decided that a *monad* is the type an object that allows you to implicitly thread a state variable through a bunch of computations, and gave up caring. So today I googled "monad threaded through computations" and found this *absolutely brilliant* tutorial: Noel Winstanley, "What the hell are monads", 1999
> 4 votes

---
Tags: reference-request, programming-languages, functional-programming, continuations
---


title: Bitarithmetrics to Base X

text:
# Question
Title: Bitarithmetrics to Base X
I've got the following theoretical problem which puzzles me a bit:

I can obtain a string of *n* bytes (as octets, one byte = one octet = eight bits) of random data. I need to preserve the randomness *while* reducing the base from 256 to *x* where *x* is below 256 (and not 0, 1, 2, 4, 8, 16, 32, 64 or 128).

As I want to preserve the randomness, I don't want to cut-off (waste) any information from this string *until* I've obtained the number of chunks I need. This is for reason of randomness which can be a limited resource on the computer.

I had the idea to do this for base64 which is simple because I can just create 4 numbers out of a single byte (by shifting bits for example: encode64()). But how to do with a base like 254 for example? I can not cut off at bit-boundaries here, can I?

Do I probably need to create a number large enough out of base 2 based bits that can contain both bases? (This is one of the ideas I have so far).

Would be great to get some feedback, I normally paint pictures with such problems, however, just discovered this website here yesterday and I normally use Stackoverflow so I thought I give it a try :D

If you're interested in some non-theoretical background to my question, see *"What is the meaning of the term “simple string” for the SALT string in Unix crypt using SHA-256 and SHA-512?"*, you might get an idea why I don't want to loose any information bits from the random source.

# Answer
You can use "arithmetic decoding". Interpret your random data as a random bit stream which encodes a random number between $0$ and $1$. Then write this number in base $B$.

A much simpler method is "rejection sampling". Suppose for example that $128 \< B \< 256$. Given a random byte $x$, if $0 \leq x \< B$ then output $x$, otherwise reject. If $x$ is close to $256$ then this is pretty efficient. (To get higher efficiency, try the same trick with some power of $B$, i.e. output several digits at once.)
> 6 votes

---
Tags: binary-arithmetic
---


# Question
Title: Find out whose turn it is to buy the croissants
A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The purpose of this question is to determine an algorithm for deciding whose turn it will be to bring croissants tomorrow.

Constraints, assumptions and objectives:

* Whose turn it is to bring croissants will be determined the previous afternoon.
* On any given day, some people are absent. The algorithm must pick someone who will be present on that day. Assume that all absences are known a day in advance, so the croissant buyer can be determined on the previous afternoon.
* Overall, most people are present on most days.
* In the interest of fairness, everyone should buy croissants as many times as the others. (Basically, assume that every team member has the same amount of money to spend on croissants.)
* It would be nice to have some element of randomness, or at least perceived randomness, in order to alleviate the boredom of a roster. This is not a hard constraint: it is more of an aesthetic judgement. However, the same person should not be picked twice in a row.
* The person who brings the croissants should know in advance. So if person P is to bring croissants on day D, then this fact should be determined on some previous day where person P is present. For example, if the croissant bringer is always determined the day before, then it should be one of the persons who are present the day before.
* The number of team members is small enough that storage and computing resources are effectively unlimited. For example the algorithm can rely on a complete history of who brought croissants when in the past. Up to a few minutes of computation on a fast PC every day would be ok.

This is a model of a real world problem, so you are free to challenge or refine the assumptions if you think that they model the scenario better.

Origin: Find out who's going to buy the croissants by Florian Margaine. My reformulation here has slightly different requirements.

# Answer
There are two categories of solutions to this sort of problem that I'm aware of: *biased lotteries* and *filtered/generated random sequences*.

First, let's dispense with easy but wrong solutions that keep no state. Any lottery-style solution that maintains no state will have the number of wins in a binomial distribution, which fails the "as many times" criterion. You can select a random sequence that picks all people equally (just going around the list does that; permutations provide randomness), but once people start going on vacation your sequence now has holes. Unless you keep track, you will again find yourself with binomial distributions instead of maintenance of equal effort.

Let's also commit to having actual randomness. You might want this so that, for instance, a person cannot schedule their vacation on the basis of a deterministic algorithm so that they are never present when it is their turn to buy croissants (until they use up all their vacation days, I suppose).

So, on to the two types of solutions.

1. To construct a biased lottery, first note that we can pick from pretty much *any* continuous distribution (with finite deviation) to generate numbers for our lottery. The loser can then be the person with the lowest number. Then the simplest bias is to keep track of whether each individual has bought more or less than their share. You can measure the bias in units of croissants. You can tune the degree of randomness by changing the width and shape of the distribution--this will also determine how far away any individual can get from "the same number of times". Gaussians are easy; they allow for reasonable surprise without having tails that are too long ("unfair"). So the basic shape of the solution is (in Scala code)

```
case class Employee(var bias: Double) {
  def eat         { bias -= 1 }
  def buy(n: Int) { bias += n }
  def roll        = bias + stdev * Random.nextGaussian
}

```

You can keep track of who bought last and give them a hefty bias bonus (e.g. `10*stdev`) to keep people from buying twice in a row save in the edge case where vacation structure allowed everyone to have bought "last" time. (i.e. you buy, then go on vacation.) Same thing for not being present on the day they're selected. (If someone is absent every other day they eventually *will* come up as they burn through their bias bonus; I consider this a feature rather than a bug.)

So, you collect your list of present employees for the day, have them all roll for the lottery, pick the lowest, and update. You can choose whether to have the buying bonus be equal to the number of employees (good when the cost is negligible but the trip to get croissants is burdensome), the number of employees present (good if the trip is easy but the cost is burdensome), or something in between (to acknowledge both burdens). It's probably better to only have the "eat" penalty for people who are present, but you can do it either way if you feel that merely being on vacation doesn't give you a right pitch in less.
2. To construct a filtered random sequence, first you need to generate a random sequence. Shuffling a list of the employees is as good a way as any to start. Just go through the list, in order, from day to day. If someone can't buy because they're absent or can't be told or bought before, skip them. Now you have a problem: you're accumulating people who have been skipped. That's okay, though. When you get to the end of your sequence, append the list of skipped employees to the full list before shuffling. Now the probability of coming up is proportional to the number of times you've been skipped, which maintains the "same number of times" property.

If you use a standard shuffle, it's also particularly easy to quantify the randomness when there are no vacations. If you picked people completely at random, the knowledge of who was to bring next would contain $\log\_2(N)$ bits of information if there were $N$ employees. Instead, however, only $N!$ instead of $N^N$ possible sequences are allowed, so the information is reduced by $\log\_2\left\[\left( {N!} \over {N^N} \right)^{1/N}\right\] \approx -{1 \over {\log(2)}} + {\log\_2{\sqrt{2 \pi / N}} \over N } \approx -1.4$ bits (for large $N$; for $N=10$ it's $~1.14$).

Personally I favor the biased lottery solution as the control over the randomness is better. With filtered sequences, you can come up with more complex ways to generate sequences. For example, rather than taking a random permutation, perform local swaps out to a certain distance, or allow swapping of people out of the pool entirely (but they go onto the skipped-list)—but these things require more algorithmic effort. With the lottery, you just adjust the standard deviation.
> 7 votes

# Answer
Let $\\{P\_1,...,P\_n\\}$ be the set of croissant's byers. Let ${v\_i}^k-1$ be the amount spent by $P\_i$ on croissant up to the day $k$ (it can be the number of times he buy croissant if they always spend the same money whatever the number of peoples present, which don't look clever enough for our croissants lover); the $-1$ is for initialisation and to avoid division by $0$.

For some parameter $l$, let $v^k=\sum\_{i=1}^n ({v\_i}^k)^l$.

At day $k$, they choose the next day's croissant's buyer by firing a random variable that outcome $i$ with probability $1-\frac{(v\_i^k)^l}{v^k}$. If the chosen one is not here (today or the day after) they toss the coin again until they find a suited one (he does exists, because they are mostly here every day...).

And they lived happily until they find out that $P\_1$, that coward, was there, only one day over two, and so, never buys any croissant!

After some reflection (and may be a bit of torture on $P\_1$ so that he refund the croissant he eat without paying) they modifies a their algorithm.

They compute the average price of croissant they pay every day and call it $v$.

On the first day they compute a planning of buyers for the days to come. To do so they do as before with the random variable, and updating the $v\_i^k$ by the price they should have paid on day $k$, i.e. adding $v$ each time they are planned to go to the baker. Because they are clever and they don't want to pay too much they also remember how much they really paid at day $k$ so that when they will update the planning no one is penalised.

They plan, until every $P\_i$ has a date in the future where he should buy croissant.

If $P\_i$ was planned to buy croissant on day $k+1$ but announces that he can't on day $k$ (or if he hasn't be warmed) he give his place to someone present that has no obligation the following day e.g. $P\_j$ and he take the next turn of $P\_j$.

The day when the first of the $P\_i$ is not planned to buy croissant in the future, they prolong their planning (with the random variable computed with the $v\_i^k$ updated to the real amount they have paid and the amount planned) until everyone is back on the line.

And when this goes forever, they live happy, sharing equally the price of croissant.

But $P\_1$ is not happy. Indeed, he think that the chosen $l$ is too small and so the probability of paying twice in a row too big. Whatever ... The others let him choose $l$ as large as he wants. Because he is grumpy but not stupid, he chose $l=k$ that way as time pass even if the ratio between big payers and small players tend to not be seen the big $l$ tend to emphasize it.

Still $P\_1$ is not so happy, he is there only half of the days (so half of the croissant) and has to pay as much as $P\_2$ that is here every days. Unfair!

But because they are tired of grumpy $P\_1$, they chase in away. But in the corner of their head they are still thinking of changing the $v\_i^k$ in the difference between what they paid and what they eat (normalized to get positive values) but they are too lazy and too full of croissants.

***Ps: Sorry for the bad English but I'm not native speaker and it's late ...*** please feel free to correct mistakes (and may be add so spices to the story ...)
> 4 votes

# Answer
Every iteration you have

* A list of people who are present and available to buy
* The previous buyer

If you pick a person at random among the people in the list and excluded the previous buyer, you achieve your objectives:

1. The algorithm is "maximally" random as we use the *minimum* amount of information from the previous iteration and choose randomly.
2. On average people pay for (N/(N-1)) croissants every time they participate in an extraction making the algorithm as fair as possible.
3. I would suggest to eliminate the no-repeat rule to make this maximally random.

Other algorithms I've seen proposed are less random or less fair:

1. "Deck shuffle" algorithms are not really random in the sense that the probability to have to pay is not constant (1/N in the first pick, 1/(N-1) in the second... 1 at the Nth pick -- if one hasn't been picked yet). Furthermore, if you are picked first, you have exactly zero chances to be picked for the next N times. The system is easily broken by coming in rarely until picked and then constantly.
2. "Compensative" algorithms that try to actively make everyone get the same number of croissants instead of relying on the properties of random numbers fail to be random or fair (or both).
> 2 votes

---
Tags: algorithms, scheduling
---


# Question
Title: Do expressions have much to do with referential transparency?
In other words, can a programming language be referentially transparent even if not everything is an expression?

And can you say that if in a programming language, everything is an expression, then it is referentially transparent?

# Answer
> 2 votes
I think the question is a bit poorly stated because it uses the term "expression" in an unclear way. So for the purposes of this answer let us say that an *expression* is a term which does not trigger any computational effects (such as divergence, I/O, mutation of state, exceptions, etc.). In Algol-like languages the opposite of expression is a *command*. I will say *term* for any piece of syntax.

I shall take *referential transparency* to mean that we may replace a term with its value without changing the program. More precisely, we obtain an observationally equivalent program when we replace the term with its value. Note however that referential transparency is *not* sensitive to *efficiency*, as replacing a term with its value almost always results in a more efficient program.

For example:

* `print "Hello, world!"` is not referentially transparent because it returns the unit value (`void` is a horrible, horrible misnomer because it suggests that *no value* is returned, when in fact the *trivial* value is returned; in contrast, raising an *exception* return no value) -- if we substitute the unit value, the program won't print anything anymore
* `x = x + 3` is not referentially transparent because it changes state (the value of `x`)
* `3 + 4` is referentially transparent because we may substitute it with `7` safely
* `while true do skip done` is an infinite loop, which is not referentially transparent. If we replace it just with `skip` (the unit value) then the program might do things it otherwise would not, such as launch missiles.

I hope you see now why your question is unclear. If you define "expression" as "free from all effects" then almost by definition it will be referentially transparent. If you define "expression" syntactically as "such and such syntactic forms are expressions", then we would have to check whether the syntax allows us to construct terms which are not referentially transparent.

One more point: it does not make sense to say that a programming language is referentially transparent, but rather that a particular term or a program is referentially transparent. So we should interpret the question from the first sentence as "if a programming language contains terms that trigger computational effects, must it have some non-transparent terms?", and I think then "yes" is the obvious answer because we just consider a command which triggers a computational effect.

You then ask about languages in which "everything is an expression". Well, that would be a *pure* language whose only possible effect is non-termination (because of infinite recursive calls). Depending on the language evaluation strategy this may or may not cause expressions to be referentially non-transparent. For example, in Haskell sometimes it does not matter that an expression is non-terminating because Haskell won't evaluate it until it is needed, which may be never. But in general non-termination is the thing to worry about in a pure language.

There are languages in which all terms are referentially transparent by design. Such languages cannot be Turing complete, however (assuming they have sane syntax). An example is Agda, which does not allow you to write a non-terminating expression, but it is still very powerful as a programming language, and a proof assistant.

A far more interesting question is whether a term can be referentially transparent even though it triggers computational effects. The answer is positive, and useful. Many data structures are self-modifying but they look referentially transparent from the outside, let me just mention splay trees as a famous example. Another example are caching strategies where lookups are cached (state change) so that they may be answered faster in the future. It is an interesting challenge for programming languages to properly account for such phenomena so that compilers can see what is going on and take advantage of the situation. For example, in a splay tree we may reorder lookups and updates, or if we work with two splay trees it does not matter which tree we work with first (so long as the data is not migrating between them). Note however.

I hope that answers your questions a bit by putting them into wider context.

---
Tags: programming-languages
---


title: Tokenizer and complex operators

text:
# Question
Title: Tokenizer and complex operators
I'm trying to create simple tokenizer to transform following (only part shown) search expression to tokens

```
word1 near(1) word2

```

where word1, word2 are some words and near(1) is distance operator. The question is how this expression should be tokenized. I see two ways

```
1. <WORD, word1> <WORD, near> <LPAREN> <NUMBER,1> <RPAREN> <WORD, word2>.
2. <WORD, word1> <NEAROP, 1> <WORD, word2>

```

But should I really try to tokenize NEAR(\d+) during tokenization, or should I go first way and handle NEAR operator at parser level, during building parse tree?

# Answer
> 1 votes
Since you indicate that the parameter of the near operator can be an arbitrary expression, it should be handled at the parser rather than at the lexer. Otherwise how would you handle things like near(x+y)?

---
Tags: parsers
---