# Question
Title: Approximation of minimum bandwidth on binary trees
Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes.

The decision problem is NP-complete even for binary trees. Complexity Results for Bandwidth Minimization. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, No.3, 1978.

What is the best known efficient approximability result for computing minimum bandwidth on binary trees? What is best known conditional hardness of approximation result?

# Answer
Blache et. al, On Approximation Intractability of the Bandwidth Problem, 1997 confirms there is no **PTAS** for the problem unless $\text{P} = \text{NP}$, even for (binary) trees. Unger W, The Complexity of the Approximation of the Bandwidth Problem, 1998 show that for any constant $k \in \mathbb{N}$ there is no polynomial time approximation algorithm with an approximation factor of $k$. So, unfortunately there's no **PTAS** nor **APX** for the problem.

However, for some types of graphs, the problem can be solved or approximated in polynomial time. For a recent survey, see Petit J., Addenda to the Survey of Layout Problems, 2011. In the survey, see Tables 3, 4 and 8. The survey also gives a nice list of references if you want to dig in deeper to some direction. This is an more updated version of the older survey by Diaz et al., A survey of Graph Layout Problems, 2002.

In case you are interested in the exact algorithm as well, I think currently the fastest one is given by Cygan M. and Pilipczuk M., Even Faster Exact Bandwidth, 2012. The algorithm runs in $O(4.83^n)$ time.
> 7 votes

---
Tags: complexity-theory, np-complete, reference-request, approximation
---


title: About Codd's reduction algorithm

text:
# Question
Title: About Codd's reduction algorithm
Codd's Algorithm converts an expression in tuple relational calculus to Relational Algebra.

1. Is there a standard implementation of the algorithm?
2. Is this algorithm used anywhere? (It seems that the industry only needs SQL and variants, I'm not sure about database theorists in academia.)
3. What's the complexity of the reduction?

<sub> This was posted on SO over a year ago, but it didn't receive a good answer. </sub>

# Answer
> 9 votes
This reduction is the constructive proof technique to show that a subset (named safe) Tuple Relational Calculus (TRC) is less expressive than Relational Algebra (RA). The other way being true too, Safe-TRC and RA have equivalent expressive power. See Theorem 5.3.10 for instance. The syntactic "safety" restriction ensures the domain independent property of the calculus and is needed.

In R-DBMS, SQL can be seen as the concrete (declarative) language for TRC. The RA counterpart is the procedural plan (a sequence of operations) in which an SQL expression is compiled to. So, the conversion is actually the formal description of the compilation process. Note that SQL introduces extensions like DISTINCT, ORDER BY, GROUP BY which are clearly outside the scope of TRC and RA theory.

I don't know the precise theoretical complexity of the conversion, but clearly it has to be "cheap". Photon Kolaitis states that it is linear.

I'm not aware of a proof-of-concept implementation of this algorithm.

---
Tags: algorithms, database-theory
---


title: Regular sets have linear growth?

text:
# Question
Title: Regular sets have linear growth?
Is it true that the set $\\{ 0^{n^2} \mid n \in\mathbb{N} \\}$ is not regular because it does not grow linearly?

> Regular sets are called regular because if you have a regular set then you can always pump it up (pumping lemma) in regular intervals and get other things in the set. They string out at very linear intervals. That's why anything that grows in other than linear intervals is not regular.

Therefore, $\\{ a^{n^2} b^n \mid n \in\mathbb{N} \\}$ is not regular, right? Also, I know that $\\{ a^n b^n \mid n \in\mathbb{N} \\}$ is not regular, but what about $\\{ a^{cn} b^{dn} \mid n \in\mathbb{N} \\}$ for any integer coefficients $c$ and $d$?

# Answer
> Is it true that the set $0^{n^2}$ is not regular because it does not grow linearly?

Yes, that's true. That follows from the pumping lemma as explained in the paragraph you quoted.

> Therefore, $a^{n^2} b^n$ ... is not regular?

Yes, that's also true for the same reason.

> Also, I know that $a^n b^n$ is not regular, but what about $a^{cn} b^{dn}$ for any integer coefficients $c$ and $d$?

The language $\left\\{a^{cn} b^{dn} \mid n \in \mathbb{N}\right\\}$ where $c$ and $d$ are fixed is regular if and only if $c$ or $d$ is equal to 0.
> 5 votes

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


title: Most efficient know way to match orders

text:
# Question
Title: Most efficient know way to match orders
Consider two 2D-Array $B\_{ij} $ (the buy array) and $S\_{ij}$ (the sell array) where each $i^{th}$ element is associated with an array of floating-point values and each of the floating point value, in turn, is associated with an array of integers.

For example

```
B = [
  0001 => [ 32.5 => {10, 15, 20},
            45.2 => {48, 16, 19},
            ...,
            k1
          ],
  0002 => [ 35.6 => {17, 35, 89},
            68.7 => {18, 43, 74},
            ...,
            k2
          ]
]

```

and similiarly for the sell array.

This is akin to an order association system of a stock/commodity exchange

```
BuyOrderBook = [
                 CompanyName => [
                                 Price1 => [Qty1, Qty2...],
                                 Price2 => [Qty1, Qty2...]
                                ]
                 SecondCompany = [...]
               ]

```

What is the fastest way known to solve the following problem:

> **Input:** Buy array $B$, Sell array $S$
> **Problem:** Decide wether there are $(c\_1 \Rightarrow p\_1 \Rightarrow q\_1) \in B$ and $(c\_2 \Rightarrow p\_2 \Rightarrow q\_2) \in S$ with $q\_1, q\_2 \> 0$ and $p\_2 \geq p\_1$.

In short, what is the fatest way of matching orders for an exchange?

**Update in response to comments**

Lets say, MSFT has 25 shares @ \\$60 to be sold and there is buyer who is willing to offer \\$61 for 10 shares of MSFT. Then the buyer gets 10 shares @ \\$60 and the buy order book becomes empty while the sell order book now is updated with new quantity - 15 shares @ \\$60.

Now take the reverse case, MSFT has 25 shares @ \\$60 to be bought and there is seller who is willing to receive \\$61 for 10 shares of MSFT. Then the trade will not be executed because seller is demanding a minimum of \\$61 and the buyer is offering a maximum of \\$60. The orders are now stored and await until new orders are received.

(This is the limit order principle, where the seller specifies minimum price at which he is willing to sell at and buyer specifies maximum price at which he is willing to buy).

Post execution, the sell order book will be (25-10)=15@86.5 while buy order book will be empty (10-10)=0.

# Answer
> 5 votes
Maintain your buy-order book as an array of companies. For each company, keep a priority queue of prices (max for buy and min for sell). For each price, keep a queue of orders.

To check for matching orders, for each company, call `find-min()` and `find-max()` on the company in the sell array and buy array to find the best buy/sell prices. If max \> min, then try to fulfill the order. To fulfill the order, pull elements off of your buy and sell queues for that company and price, until one of your price queues is empty. When the price queue is empty, delete the corresponding element from its priority queue, and perform the check again.

This strategy costs constant time per order, and $O(\log p\_i)$ per price change, where $p\_i$ is the number of prices for company $i$.

---
Tags: algorithms
---


# Question
Title: Pattern classification: what goes into the sample?
I am trying to compare the performance of a classification result with Bayes classifier, K-NN, Piece wise component analysis (PCA). I have doubts regarding the following (please excuse my lack of programming skills since I am a biologist and not a programmer thus finding the Matlab documentation hard to follow).

In the Matlab code

```
    Class = knnclassify(Sample, Training, Group, k)
    Group =  [1;2;3]   //where 1,2,3 represents Class A,B,C respectively.

```

What goes in the sample because my data is a 100 row 1 column for each of the classes? So Group 1 contains data like $\[0.9;0.1;......n\]$ where $n=100$. Would the sample be a vector containing random mixtures of the data points from the three classes? Same question for the `Training` matrix.

# Answer
First a bit about the classifier: The knn classifier works by majority voting. It takes an input record, finds the k nearest labeled data points, looks at the class labels on each data point and assigns the current record the most common class label. For instance, if I use a 3-NN classifier and my three neighbors are of class \[1 1 2\], then I will select class 1 for this record.

That being said, "Training" should contain the feature vectors of your labeled dataset (probably 1 record per row). "Group" contains the class label for the corresponding record. So the $i^{th}$ value in Group is the class label associated with the $i^{th}$ record in "Training". "K" specifies the number of neighbors you'd like to look at when classifying new objects. Lastly, "Sample" will be the data point you want to classify.

Also, I've never heard of piece-wise component analysis, do you mean Principle Component Analysis? If this is the case, just note that PCA is a method commonly used for dimensionality reduction, so you'll still have to use a classifier to get labels for your data.

One more note: Matlab has an SVM classifier as well, its calls are similar to that of the Naive Bayes classifier for training and testing.
> 4 votes

---
Tags: machine-learning, modelling, pattern-recognition
---


title: Lambda Calculus Evaluation

text:
# Question
Title: Lambda Calculus Evaluation
I know this is a simple question but can someone show me how $(\lambda y. \lambda x. \lambda y.y) (\lambda x. \lambda y. y)$ reduces to $\lambda x. \lambda y. y$.

# Answer
The reason that $(\lambda y. \lambda x. \lambda y.y) (\lambda x. \lambda y. y)$ reduces to $\lambda x. \lambda y. y$ and not to $\lambda x. \lambda y.\lambda x.\lambda y.y$ is that the $y$ in the body of $\lambda y.\lambda x.\lambda y.y$ refers to the argument of the third lambda, not the first.

If you rename the arguments to have distinct names, $\lambda y.\lambda x.\lambda y.y$ would be written as $\lambda y\_1.\lambda x.\lambda y\_2.y\_2$. So if you apply that function to the argument, that means that every occurrence of $y\_1$ in $\lambda x.\lambda y\_2.y\_2$ should be replaced with the argument. However $y\_1$ does not appear at all in that expression, so the argument is simply ignored and the result is just $\lambda x.\lambda y\_2.y\_2$.
> 10 votes

---
Tags: logic, lambda-calculus
---


# Question
Title: reduce reduce and shift reduce error in LALR grammar
I have to write a grammar for Pascal, and there is just one thing that is causing problems.

Lets say we have operators (sorted by priority from low to high):

1. *Postfix `^`*.
2. *Prefix `^`*.
3. *`[ ]`*, and `.`, (same priority and left associative).
4. The only terminal is `id`, which is any lowercase letter.

Now let's say that an expression is:

1. Any id.
2. Any expression with the *Postfix `^`* operator.
3. Any expression with the *Prefix `^`* operator.
4. Any expression with `.` followed by `id`.
5. Any expression with `[` and another expression and `]`.

Now I would like to know how can I make a LALR grammar without shift-reduce and reduce-reduce conflicts, OR if that can't be done how can I prove that it can't be done.

Some examples:

```
good:
a.b.c.d
a.b^.c
^a.b^
a.b^^[c]^^.d.e
^^a.b^.d.e^[]

bad:
a.^b.c

```

Without the prefix `^`, this problem is easy to solve, but the prefix sign keeps getting me. Can anyone help? My solutions so far:

```
// this works without the prefix but it does not produce a.b^.c which is wrong.
A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] | C . id;

```

So I thought that the prefix can only occur before the first dot, and between dots, there can only be a postfix `^` and brackets. So I came up with this:

```
A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] |id D;
D ::= id E;
F ::= E | F ^;
E ::= id | F . id;

```

But this causes 3 conflicts.

# Answer
> 4 votes
I don't see any problem with your first grammar and bison doesn't complain on the rendering I've done of it.

I (and bison) see one conflict in your second grammar (which doesn't describe the same language as the first BTW). After having seen `id id id` with a pending `^`, you don't know if your last `id` and the `^` should be an F, or if you should keep together the three id forming an A which will be gathered with the '^'.

---

Edit after your comment:

A direct rendering of your rules:

```
EXP ::= id | EXP ^ | ^ EXP | EXP . id | EXP [ EXP ]

```

will be ambigous — and thus have conflict(s) — because you don't state if the prefix version of `^` has priority over the other (postfix) operators. I don't remember how it was in Pascal, but you can get both effects with

```
EXP ::= POST | ^ EXP
POST ::= id | POST ^ | POST . id | POST [ EXP ]

```

and

```
EXP ::= PRE | EXP ^ | EXP . id | EXP [ EXP ]
PRE ::= id | ^ PRE

```

Edit again: a mixed version corresponding to my understanding of what you ask in the comment (I continue to find this confusing and I consider the complexity of the grammar — with post operators given twice — as a hint it is so :-) )

```
EXP ::= PRE | POST2
POST2 ::= PRE '^' | POST2 '^' | POST2 '.' id | POST2 '[' EXP ']'
PRE ::= POST | '^' PRE
POST ::= id | POST '.' id | POST '[' EXP ']'

```

---
Tags: programming-languages, parsers, formal-grammars
---


# Question
Title: Regular Expression for the language that requires one symbol to occur at least once
I am trying to figure out the simplest way to do this using a regular expression.

* Three symbols a, b, c.
* The sequence length is unlimited, i.e. \*.
* The symbol a must be somewhere in the sequence at least once, but can appear more than once.
* The sequence may have only a.

More formally, $\\{ w \in \\{a,b,c\\}^\* ~|~ \\#\_a(w)\ge 1 \\}$, where $\\#\_a(w)$ is the number of $a$s in $w$.

The best I get is

> $( ( b \mid c )^\*\\, a\\, ( b \mid c )^\* )^+$

Is that the simplest way?

# Answer
The simplest regular expression I can think of for this is $\left(a \mid b \mid c\right)^\* a \left(a \mid b \mid c\right)^\*$. This is simpler than yours by the following measures of complexity:

* It contains less nesting (and fewer parentheses in general)
* It contains fewer quantifiers
> 7 votes

# Answer
As the expression is to be part of a parser (i.e. should be efficiently checkable), it might be a good idea to make the regular expression unambiguous:

$\qquad \displaystyle (b \mid c)^\*\\, a\\, (a \mid b \mid c)^\*$

describes the same language but avoids ambiguity by distinguishing the *first* $a$ in a matching word. Wether this has an impact depends on the way your parser generator works.

This is the same written as diagram, with the token names the OP uses:
*Image by Guy Coder.*
> 5 votes

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


# Question
Title: Why is using a lexer/parser on binary data so wrong?
I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also context sensitive. This basically leads to having only one type of token, a token for byte.

Can someone explain why parsing binary data with a lexer/parser is so wrong with enough clarity for a CS student who hasn't taken a parsing class, but with a footing on theory?

# Answer
> 10 votes
In principle, there is nothing wrong.

In practice,

* most non-textual data formats I know are not context-free and are therefore not suitable for common parser generators. The most common reason is that they have length fields giving the number of times a production has to be present.

Obviously, having a non context-free language has never prevented the use of parser generators: we parse a superset of the language and then use *semantic rules* to reduce it to what we want. That approach could be used for non-textual formats if the result would be deterministic. The problem is to find something else than counts to synchronize on as most binary formats allow arbitrary data to be embedded; length fields tell you how much it is.

You can then start playing tricks like having a manually writen lexer able to handle that with feedback from the parser (lex/yacc handling of C use that kind of tricks to handle typedef, for instance). But then we come to the second point.
* most non-textual data formats are quite simple (even if they are not context-free). When the counts mentioned above are ignored, the languages are regular, LL1 at worst, and are thus well suited for manual parsing techniques. And handling counts is easy for manual parsing techniques like recursive descent.

# Answer
> 7 votes
Let's categorize data into three categories: data readable by humans (usually texts, varying from books to programs), data intended to be read by computers and other data (parsing images or sound).

For the first category, we need to process them into something a computer can use. As the languages used by humans can generally be captured relatively well by parsers, we usually use parsers for this.

An example of data in the third category would be a scanned image of a page out of a book which you want to parse into text. For this category, you almost always need very specific knowledge about your input, and therefore you need a specific program to parse it. Standard parsing technology won't get you very far here.

Your question is about the second category: if we have data that is in binary, it is almost always a product of a computer program, intended for another computer program. This immediately also means that the format the data is in is chosen by the program responsible for its creation.

Computer programs almost always produce data in a format that has a clear structure. If we parse some input, we are essentially trying to figure out the *structure* of the input. With binary data, this structure is generally very simple and easy to parse by computers.

In other words, it's normally a bit of a waste to figure out the structure of an input for which you already know the structure. As parsing isn't free (it takes time and adds complexity to your program), this is why using lexers/parsers on binary data is 'so wrong'.

# Answer
> 0 votes
If a language needs to be parsed in some non-trivial way, it usually means that structural elements need to be matched, so the input language contains **redundancy**, either because multiple inputs map to the same parse tree or because some input strings are invalid. Humans like redundancy. For example, most humans find binary operators more readable than a pure prefix or suffix notation for elementary arithmetic: $a + b \times (c - d) + e$ rather than `(+ a (* b (- c d)) e)` or `a b c d - * + e +`. The usual mathematical notation has more redundancy than Lisp (which requires more parentheses, but gets variable arities for free, so requires fewer symbols to express expressions using large arities) or RPL (which never needs parentheses). Such redundancy is rarely useful to computers — and where it is, which is when there may be errors in the data, the error correction logic is usually kept separate from the functional meaning of the data, for example using error correcting codes which apply to arbitrary byte sequences regardless of what they represent.

Binary formats are usually designed to be compact, which means few simple language features such as balanced parentheses that are expressible by context-free grammars. Furthermore, it is often useful for binary representations of data to be canonical, i.e. to have a single representation of each object. This rules out sometimes-redundant features such as parentheses. Another, less commendable consequence of having less redundancy is that if every input is syntactically correct, it saves on the error checking.

Another factor against nontrivial parsers for binary data is that a lot of binary formats are designed to be parsed by low-level code that likes to operate in constant memory with little overhead. Fixed sizes are prefered when applicable to allowing arbitrary repetition of an element. A format such as TLV that allows a left-to-right parser to allocate the right amount of memory for an object first, then read the representation of the object. Parsing from left to right is an advantage because it allows the data to be processed as it comes, with no intermediate buffer.

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


title: Complexity of Towers of Hanoi

text:
# Question
Title: Complexity of Towers of Hanoi
I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments.

* **Is it in NP?**  Attempted answer: Suppose Peggy (prover) solves the problem & submits it to Victor (verifier). Victor can easily see that the final state of the solution is right (in linear time) but he'll have no option but to go through each of Peggy's moves to make sure she didn't make an illegal move. Since Peggy has to make a minimum of 2^|disks| - 1 moves (provable), Victor too has to follow suit. Thus Victor has no polynomial time verification (the definition of NP), and hence can't be in NP.
* **Is it in PSPACE**  ? Seems so, but I can't think of how to extend the above reasoning.
* **Is it PSPACE-complete?**  Seems not, but I have only a vague idea. Automated Planning , of which ToH is a specific instance, is PSPACE-complete. I think that Planning has far more hard instances than ToH.

**Updated** : Input = $n$, the number of disks; Output = disk configuration at each step. After updating this, I realized that this input/output format doesn't fit a decision problem. I'm not sure about the right formalization to capture the notions of NP,PSPACE, etc. for this kind of problem.

**Update #2** : After Kaveh's and Jeff's comments, I'm forced to make the problem more precise:

> Let the input be the pair of ints $(n,i)$ where $n$ is the number of disks. If the sequence of moves taken by the disks is written down in the format (disk-number,from-peg,to-peg)(disk-number, from-peg, to-peg)... from the first move to the last, and encoded in binary, output the $i$th bit.

Let me know if I need to be more specific about the encoding. I suppose Kaveh's comment applies in this case?

# Answer
> 9 votes
No, the problem you've described is actually quite easy. The high-level reason is that the index $i$ is roughly $n$ bits long, so we can actually afford to spend time polynomial in $n$.

Consider the following related problem: Given two integers $n$ and $k$, describe the $k$th move in the solution of the $n$-disk puzzle. The input size is $\lg n + \lg k \< n + \lg k$, but in fact, **only the least significant bit of $n$ matters.** So even if $\lg k$ is significantly smaller than $n$, we can solve this problem in time polynomial in $O(\log k)$.

Suppose the disks are numbered from $0$ to whatever in increasing order by size, and pegs are numbered 0=source, 1=destination, and 2=spare. Let us write $k = (2p+1)\cdot 2^d$ for some integers $p$ and $d$. Then on turn $k$:

* If $d+n$ is odd, then disk $d$ moves from peg $(p\bmod 3)$ to peg $((p+1)\bmod 3)$.
* If $d+n$ is even, then disk $d$ moves form peg $(-p\bmod 3)$ to peg $((-p-1)\bmod 3)$.

We can easily compute $p$ and $d$ in time $O(\log k)$ by looping through the binary representation of $k$ from the least significant bit upward. That's it.

Now suppose you really want the $i$th bit in the output sequence, where $i$ is part of the input instead of $k$. If every turn is encoded using the same number of bits — specifically, $\lg(n+1)$ bits for the disk number, $2$ bits for the from-peg, and $2$ bits for the to-peg — then we just have to compute the $k$th move, where $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$, and then extract the appropriate bit. (Notice that $\lg(n+1)+4$ is linear in the input size, since we need to know $n$ to determine the output.)

On the other hand, if we're using a variable-length representation for the disk numbers, then we can find the move number $k$ in polynomial time by binary search. We need to know the total number of turns needed to move the top $m$ disks, for all $m\le k$, but this is given by the recurrence $$ M(m) = 2M(m-1) + (\text{\\#bits to record moving disk } m) $$ which we can evaluate in polynomial time by dynamic programming. The remaining details are left as a boring exercise for the reader.

(I assume I've made at least one off-by-one or parity error, but hopefully the main idea is clear.)

---
Tags: complexity-theory, time-complexity, towers-of-hanoi
---


# Question
Title: Non-Parametric Methods Like K-Nearest-Neighbours in High Dimensional Feature Space
The main idea of k-Nearest-Neighbour takes into account the $k$ nearest points and decides the classification of the data by majority vote. If so, then it should not have problems in higher dimensional data because methods like locality sensitive hashing can efficiently find nearest neighbours.

In addition, feature selection with Bayesian networks can reduce the dimension of data and make learning easier.

However, this review paper by John Lafferty in statistical learning points out that non-parametric learning in high dimensional feature spaces is still a challenge and unsolved.

What is going wrong?

# Answer
> 5 votes
This problem is known as the curse of dimensionality. Basically, as you increase the number of dimensions, $d$, points in the space generally tend to become far from all other points. This makes partitioning the space (such as is necessary for classification or clustering) very difficult.

You can see this for yourself very easily. I generated $50$ random $d$-dimensional points in the unit hypercube at 20 evenly selected values of $d$ from $1..1000$. For each value of $d$ I computed the distance from the first point to all others and took the average of these distances. Plotting this, we can see that average distance is increasing with dimensionality even though the space in which we are generating the points in each dimension remains the same.

Average distance vs. dimensionality

# Answer
> 3 votes
Not a complete answer, but the wikipedia page you cited states:

> The accuracy of the k-NN algorithm can be severely degraded by the presence of noisy or irrelevant features, or if the feature scales are not consistent with their importance.

The likelihood of this occurring increases in the presence of high dimensional feature spaces.

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: How to determine likely connections in a social network?
I am curious in determining an approach to tackling a "suggested friends" algorithm.

Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. These users normally (excluding the edge cases in which a user specifically recommends a friend) have a highly similar network to oneself. That is, the number of friends in common are high. I assume Twitter follows a similar path for their "Who To Follow" mechanism.

Stephen Doyle (Igy), a Facebook employee suggested that the related newsfeed that uses EdgeRank formula which seems to indicate that more is to valued than friends such as appearance is similar posts. Another user suggested the Google Rank system.

Facebook states their News Feed Optimization as $\sum u\_{e}w\_{e}d\_{e}$ where

$u\_{e}$ = affinity score between viewing user and edge creator
$w\_{e}$ = weight for this edge (create, comment, like, tag, etc)
$d\_{e}$ = time decay factor based on how long ago the edge was created

Summing these items is supposed to give an object's rank which I assume as Igy hinted, means something in a similar format is used for suggested friends.

So I'm guessing that this is the way in which connections for all types are done in general via a rank system?

# Answer
> 7 votes
You can think of the social graph as a matrix $\mathbf{M}$. One approach to the problem is to first calculate $\mathbf{M}^2$, which will give all of the paths of length two between two actors in the social network. This can be seen as the weight of the connection between these friends of friends. The next step is to select the columns from the row of $\mathbf{M}^2$ corresponding to the person of interest to get the best candidates for new friends.

# Answer
> 11 votes
What you're looking for is a heuristic. No algorithm can say, given a graph of friends as the only input, whether two individuals not directly connected are friends or aren't; the friendship/acquaintance relation isn't guaranteed to be transitive (we can assume symmetry, but that might even be a stretch in real life). Any good heuristic will therefore need to be based on an understanding of how people interact, rather than some mathematical understanding of the nature of graphs of relations (although we will need to quantify the heuristic in these terms).

Suggesting friends of friends with equal probability is a relatively cheap but inaccurate heuristic. For instance, my father has friends, but I wouldn't say I'm friends with any of them (although I'd probably say I'm a friend of my father's for the purposes of, e.g., a social network). Having a person at a relatively close distance doesn't necessarily make them a great candidate.

Suggesting people to whom you have a great many extended connections also seems like a poor choice in general, because this will tend to lead to exponential growth of friends of people who pull ahead early on (the seven degrees of separation from Kevin Bacon game is an example of this).

I suggest a circuit-based model. Assume that each link is a resistor of resistance $R$. Then the best candidate for a new friend might be the individual with the lowest equivalent resistance. Here's a poorly-executed ASCII graphics example:

```
  _____
 /     \
a---c   f
|   | /
b   d---e
| \ |
g   h   i

```

Say we want to find new friends for `a`. `a`'s current friends are `b`, `c`, and `f`. We evaluate the net equivalent resistance between `a` and each of `d`, `e`, `g`, `h`, and `i`:

```
pair   resistance
(a,d)   6/7
(a,e)  13/7
(a,g)   7/4
(a,h)   1/1
(a,i)   inf

```

According to this heuristic, `d` is the best candidate friend, followed closely by `h`. `g` is the next best bet, followed closely by `e`. `i` can never be a candidate friend by this heuristic. Whether you find the results of this heuristic to be representative of real human social interactions is what's important. Computationally speaking, this would involve finding a subgraph containing all paths between two individuals (or, perhaps interestingly, some meaningfully selected truncation of this), then evaluating the equivalent resistance between the source and sink nodes.

EDIT: So what's my social motivation for this? Well, this might be a rough model of how hard it is to get in touch with, and subsequently communicate possibly significant amounts of information through, intermediaries (friends). In CS terms (rather than physics terms), this might be construed as bandwidth between two nodes in a graph. Extensions of this system would be to allow different kinds of links between people with different weights (resistance, bandwidth, etc.) and proceed as above.

# Answer
> 10 votes
There is a lot of work done on this problem as the popularity of social networking has taken off. The problem is typically termed "Link Prediction" and very good and comprehensive surveys can be found here and here. The methods range from the very simple (e.g. Jaccard similarity between nodes) to the very complex (e.g. constructing statistical models of the generative connection process). It depends a lot on the specific features you have available in your dataset (e.g. just network structure, node attributes?, edge attributes, ...), but these surveys will give you a good idea for where to start.

# Answer
> 4 votes
Disclaimer: I am wildly guessing here; I have not read any genre research.

You could look at how many connections to nodes share relatively to the number of conncetions a node has. This is a very naive (as local) idea, but here goes.

Every node $N$ (person or some other concept) has a set of connections $C\_N$. Now, given two nodes $N\_1$ and $N\_2$, suggest $N\_2$ to $N\_1$ if

$\qquad \displaystyle \frac{|C\_{N\_1} \cap C\_{N\_2}|}{|C\_{N\_1}|} \geq \alpha$

for some reasonable $\alpha \in \[0,1\]$ (and the other way round).

Another idea is more global: determine a set of nodes *similar* to the one at hand and propose connections that many of them share. So, define the set of similar nodes

$\qquad \displaystyle S\_N = \left\\{M : \frac{|C\_N \cap C\_M|}{N} \geq \alpha\right\\}$

and the set plausible suggestions by

$\qquad \displaystyle \left\\{ S : \frac{\sum\_{M \in S\_N} \[S \in M\]}{|S\_N|} \geq \beta \right\\}$

again for reasonable $\alpha, \beta \in \[0,1\]$.

In reality, you would certainly want to weight connections individually; for instance, elements of $S\_N$ that you are already connected with should have larger import than such that are far away from you.

---
Tags: algorithms, machine-learning, modelling, social-networks
---


# Question
Title: In Constraint Programming, are there any models that take into account the number of variable changes?
Consider a CSP model where changing the value of a particular variable is expensive. Is there any work where the objective function also considers the number of changes in the value of the variable during the search process?

An example: The expensive-to-change variable may be in the control of some other agent and there is some overhead of involving that agent to change the variable. Another example: The variable participates in one of the constraints, and the satisfaction of this constraint involves calling an expensive function (such as, a simulator), e.g. $z = f(x, y)$ is the constraint, and $f$ is an expensive-to-compute function. Therefore, $x$ and $y$ are expensive-to-change variables.

# Answer
It sounds like you want a cost-sensitive (cost-aware, budgeted) optimization technique. Minimizing two values (e.g. the solution of your objective and the cost of operations on $x$ and $y$) is a multicriteria optimization problem, and those tend to be very hard to solve. A common approach is to specify a budget for the maximum allowable costs and then minimize the objective function with respect to $costs(x,y) \le Budget$. This formulation tends to fit nicely into existing frameworks as an additional constraint. Of course, specifying the cost function and the allowable budget in such a way that you get meaningful solutions can be difficult - this will depend on the specific problem you are trying to solve.
> 4 votes

---
Tags: algorithms, constraint-programming
---


# Question
Title: How many shortest distances change when adding an edge to a graph?
Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \\{ (u,v) \\})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C\_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

> How big is $C = \frac{\sum\_i C\_i}{n}$?

As $C\_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$.

You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points. That is, every vertex $v$ corresponds to some point $(x,y)$ in the plane, and for an edge $(u,v)=((x\_1,y\_1),(x\_2,y\_2))$ its weight is equal to $\sqrt{(x\_2-x\_1)^2 + (y\_2-y\_1)^2.}$

# Answer
> 19 votes
Consider the following linear chain with $n+1$ nodes, $n$ edges and viciously chosen weights:

<sup>\[source\]</sup>

Clearly, the edges could have been added in order of their weights and there are $n \in \mathcal{O}(|V|)$ of them. Adding the dashed edge (which is legal) creates shorter paths for all pairs $(u\_i,b\_j)$ with $i,j = 1,\dots,k$. As $k \approx \frac{n}{4}$ and assuming that $n \in \Theta(|V|)$, both first and last row contain $\Theta(|V|)$ many nodes each and the addition causes $\Theta(|V|^2)$ many shortest path changes.

We can now move "outwards" now, i.e. add the next edge with weight $n+2$ between $u\_{k-1}$ and $b\_{k-1}$ and so on; if we continue this to $(u\_1,b\_1)$, we cause in total $\Theta(|V|^3)$ shortest path changes.

If this does not convince you, note that you can actually start this "process" with $(c\_1,c\_2)$ and work outwards from there; this way you add $\approx n$ edges which cause in total $\approx \sum\_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$ many shortest path changes---this is just impossible to draw to fit on one screen.

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


# Question
Title: Confluence proof for a simple rewriting system
Assume we have a simple language that consists of the terms:

* $\mathtt{true}$
* $\mathtt{false}$
* if $t\_1,t\_2,t\_3$ are terms then so is $\mathtt{if}\\: t\_1 \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3$

Now assume the following logical evaluation rules:

$$ \begin{gather\*} \dfrac{} {\mathtt{if}\\: \mathtt{true} \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3 \to t\_2} \text{\[E-IfTrue\]} \quad \dfrac{} {\mathtt{if}\\: \mathtt{false} \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3 \to t\_3} \text{\[E-IfFalse\]} \\ \dfrac{t\_1 \to t\_1'} {\mathtt{if}\\: t\_1 \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3 \to \mathtt{if}\\: t\_1' \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3} \text{\[E-If\]} \\ \end{gather\*} $$

Suppose we also add the following funky rule:

$$ \dfrac{t\_2 \to t\_2'} {\mathtt{if}\\: t\_1 \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3 \to \mathtt{if}\\: t\_1 \\:\mathtt{then}\\: t\_2' \\:\mathtt{else}\\: t\_3} \text{\[E-IfFunny\]} $$

For this simple language with the given evaluation rules I wish to prove the following:

**Theorem: If $r \rightarrow s$ and $r \rightarrow t$ then there is some term $u$ such that $s \rightarrow u$ and $t \rightarrow u$.**

I am proving this by induction on the structure of $r$. Here is my proof so far, it all worked out well, but I am stuck at the very last case. It seems like induction on the structure of $r$ is not sufficing, can anyone help me out?

*Proof.* By induction on $r$, we will seperate all the forms that $r$ can take:

1. $r$ is a constante, nothing to prove since a normal form does not evaluate to anything.
2. $r=$ if true then $r\_2$ else $r\_3$. (a) both derivations were done with the E-IfTrue rule. In this case $s=t$, so there is nothing to prove. (b) one deriviation was done with the E-IfTrue rule, the other with the E-Funny rule. Assume $r \rightarrow s$ was done with E-IfTrue, the other case is equivalently proven. We now know that $s = r\_2$. We also know that $t =$ if true then $r'\_2$ else $r\_3$ and that there exists some deriviation $r\_2 \rightarrow r'\_2$ (the premise). If we now choose $u = r'\_2$, we conclude the case.
3. $r=$ if false then $r\_2$ else $r\_3$. Equivalently proven as above.
4. $r=$ if $r\_1$ then $r\_2$ else $r\_3$ with $r\_1 \neq $ true or false. (a) both deriviations were done with the E-If rule. We now know that $s =$ if $r'\_1$ then $r\_2$ else $r\_3$ and $t =$ if $r''\_1$ then $r\_2$ else $r\_3$. We also know that there exists deriviations $r\_1 \rightarrow r'\_1$ and $r\_1 \rightarrow r''\_1$ (the premises). We can now use the induction hypothese to say that there exists some term $r'''\_1$ such that $r'\_1 \rightarrow r'''\_1$ and $r''\_1 \rightarrow r'''\_1$. We now conclude the case by saying $u =$ if $r'''\_1$ then $r\_2$ else $r\_3$ and noticing that $s \rightarrow u$ and $t \rightarrow u$ by the E-If rule. (b) one derivation was done by the E-If rule and one by the E-Funny rule.

This latter case, where one derivation was done by E-If and one by E-Funny is the case I am missing... I can't seem to be able to use the hypotheses.

Help will be much appreciated.

# Answer
> 8 votes
Okay, so let's consider the case that $r = \mathtt{if}\\: t\_1 \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3$, $s$ has been derived by applying the E-If rule and $t$ has been derived by applying the E-Funny rule: So $s = \mathtt{if}\\: t'\_1 \\:\mathtt{then}\\: t\_2 \\:\mathtt{else}\\: t\_3$ where $t\_1 \rightarrow t'\_1$ and $t = \mathtt{if}\\: t\_1 \\:\mathtt{then}\\: t'\_2 \\:\mathtt{else}\\: t\_3$ where $t\_2 \rightarrow t'\_2$.

The $u$ we're looking for is $u = \mathtt{if}\\: t'\_1 \\:\mathtt{then}\\: t'\_2 \\:\mathtt{else}\\: t\_3$. $s \rightarrow u$ follows from rule E-Funny and $t \rightarrow u$ follows from rule E-If.

# Answer
> 8 votes
A little terminology may help if you want to look this up: these rules are *rewriting* rules, they have nothing to do with type systems¹. The property you're trying to prove is called *confluence*; more specifically, it's *strong confluence*: if a term can be reduced in different ways at one step, they can converge back at the next step. In general, confluence allows there to be any number of steps and not just one: if $r\to^\*s$ and $r\to^\*t$ then there is $u$ such that $s\to^\*u$ and $t\to^\*u$ — if a term can be reduced in different ways, no matter how far they've diverged, they can eventually converge back.

The best way to prove a property of such inductively defined rewriting rules is by induction over the structure of the derivation of the reduction, rather than the structure of the reduced term. Here, either works, because the rules follow the structure of the left-hand term, but reasoning on the rules is simpler. Instead of diving into the term, you take all pairs of rules, and see what term could be a left-hand side for both. In this example, you will get the same cases in the end, but a bit faster.

In the case that gives you trouble, one side reduces the “if” part and the other side reduces the “then” part. There's no overlap between the two parts that change ($t1$ in \[E-If\], $t\_2$ in \[E-IfFunny\]), and there's no constraint on $t\_2$ in \[E-If\] or on $t\_1$ in \[E-IfFunny\]. So when you have a term to which both rules apply — which must be of the form $\mathtt{if}\\: r\_1 \\:\mathtt{then}\\: r\_2 \\:\mathtt{else}\\: r\_3$, you can choose to apply the rules in either order:

$$\begin{array}{rcl} & \mathtt{if}\\: r\_1 \\:\mathtt{then}\\: r\_2 \\:\mathtt{else}\\: r\_3 & \\ {\small \text{\[E-If\]}} \swarrow & & \searrow {\small \text{\[E-IfFunny\]}} \\ \mathtt{if}\\: r\_1' \\:\mathtt{then}\\: r\_2 \\:\mathtt{else}\\: r\_3 & & \mathtt{if}\\: r\_1 \\:\mathtt{then}\\: r\_2' \\:\mathtt{else}\\: r\_3 \\ {\small \text{\[E-IfFunny\]}} \searrow & & \swarrow {\small \text{\[E-If\]}} \\ & \mathtt{if}\\: r\_1' \\:\mathtt{then}\\: r\_2' \\:\mathtt{else}\\: r\_3 & \\ \end{array} $$

¹ <sub> You'll sometimes see types and rewriting together, but at their core they're orthogonal concepts. </sub>

---
Tags: logic, semantics, proof-techniques, term-rewriting
---


title: Subset Sum Requirements

text:
# Question
Title: Subset Sum Requirements
Consider the following problem.

> Given a set $S$ of integers, a function $f : \mathbb{Z} \to \mathbb{Z}$ and $k \in \mathbb{Z}$, decide wether there is $X \subseteq S$ such that $f\left(\sum\_{x\in X}x\right)=k$.

Is this still considered a subset-sum problem?

For instance, given

$\qquad \displaystyle S=\\{ −7, −3, −2, 5, 8\\}$

and $k=0$, find a subset $X$ such that $f\left(\sum\_{x\in X}x\right)=0$ for $f(y)=-3+y$. In this case, a solution is $X=\\{ -3,-2,8 \\}$.

# Answer
> 7 votes
It depends on the form of $f$. If $f(x) = x$, then it is identical to subset-sum. If $f(x) = 0$, then it is a trivial problem with an $O(1)$ solution: return $true$. You can possibly define $f$ in other ways to make the question more or less difficult, as well.

See below a mini-complexity zoo corresponding to different choices of $f$:

* for $f(x) = c$, the problem is $O(1)$ (*return true iff $c = 0$*).
* for $f(x) = 0$ for $x \geq 0$ and $f(x) = 1$ otherwise, the problem is $O(n)$ (*linear search for any number greater than 0*)
* for $f(x) = 0$ for $x \geq c$, $c \> 0$, $f(x) = 1$ otherwise, the problem is no more than $O(n \log n$) (*sort the items in the set in descending order, and see if any prefix sums to a working solution*)
* for $f(x) = ax + b$, the problem is as hard as subset-sum (in an informal sense, and I don't provide a construction to demonstrate the reduction from subset-sum to this... if I'm wrong about this one, please let me know!)
* for $f(x) = 0$ if the Turing machine encoded by $x$'s binary representation halts when given the binary representation of $x$ as input (alternatively, when given the empty tape as input, and similar kinds of halting problems), and $f(x) = 1$ otherwise, the problem is undecidable (*a solution to the problem for this $f$ could solve the halting problem*)

Anybody see anything else fun?

# Answer
> 6 votes
You can get arbitrary difficult problems depending on your $f$.

Let $A$ be a language. Define $f$ as follows: $$f(x)= \begin{cases} 0 & x\in A \\ 1 & o.w. \\\end{cases}$$

Consider set $S=\\{x\\}$. There is a non-empty subset $X\subseteq S$ s.t. $f(\Sigma\_{x\in X} x) = 0$ iff $x \in A$.

Without putting a complexity requirement on $f$ you can get problems of arbitrary difficulty.

An interesting case is when $f$ is of restricted complexity, e.g. polynomial time computable. In that case we can use it to invert $f$, so the problems can be as difficult as inverting an arbitrary polynomial time function (and assuming that there are polynomial time computable psuedo-random number generators which are hard to invert in subexponential time, it means you cannot solve the problem): let $g$ be an arbitrary polynomial time computable function. Assume that we are given $y\in Range(g)$ and we want to find an $x$ s.t. $g(x)=y$. Define $f(x)=g(x)$. Let $S= \\{0,1,2,4,8,\ldots, 2^m\\}$ for suitable large $m$ (to make sure that a preimage of $y$ can be represented as sum of the numbers in the set). At each set we will remove a number $2^i$ from the set and check if there is still a subset $X$ s.t. $f(\Sigma\_{x\in X} x)=y$. If the answer is yes, we know there is a solution that doesn't need that number, so we remove it from $S$ permanently. If the answer is no, we know that we need that number for all solutions. After $m$ steps we will have a set $S$ which is a solution and no subset of it is a solution, so we can return $x=\Sigma\_{x \in S} x$ as our answer.

On the other hand, if $f$ is polynomial time computable, the problem will be in $\mathsf{NP}$.

In the special case that the function $f$ is linear, since $\Sigma$ commutes with linear functions, the problem is the same as solving the subset-sum over $f(S) = \\{ f(x) \mid x \in S\\}$. As long as the linear function is not constant the problem will be as hard as subset-sum, i.e. $\mathsf{NP\text{-}hard}$ (if you want to solve the subset-sum instance $(S,k)$, apply $f^{-1}$ to members of $S$ to obtain $S'$ and then use the modified version on $(S',k)$ to solve it).

(This trick will also work for more general case where the function $f$ is polynomial time computable and has an inverse that is also polynomial-time computable.)

# Answer
> 0 votes
Yes, this is still subset sum problem, but instead of finding a subset whose sum is $0$, you are required to have a sum that equals something else (in your example it 3, in general it is $f^{-1}(0)$, which might be a set of numbers if $f$ is many to one).

This doesn't change much the difficulty of the problem for bijective $f$, but otherwise depends on the number of preimages $f^{-1}(0)$ has. As stated already, if $f(y)=0$, the problem becomes trivial.

---
Tags: complexity-theory
---


# Question
Title: What is the purpose of M:N (Hybrid) threading?
In other words, what advantages does Hybrid threading have over 1:1 (kernel only) and N:1 (user only) threading?

This is a follow-up to What is the difference between user-level threads and kernel-level threads?

# Answer
> 7 votes
I think hybrid threading is very similar to a thread pool.

In thread pool, you are using $N$ kernel threads to execute $M$ “tasks”, where $M$ can be much higher than $N$. The advantage over using one thread for each task (kernel only threading) is that you consume less resources, like memory (both virtual and physical) and kernel objects (at least in the specific case of Windows threads, but I imagine other OSes are similar in this regard). You also get less context switches, which increases performance (in the ideal case, where you have as many running threads as you have processors, you may have almost no context switches).

The advantage over user only threading is that you can take advantage of multiple CPUs or multiple CPU cores. And if one task blocks, you can create another kernel thread to use the available CPU more efficiently.

So, you get the advantages of both approaches, at the expense of some additional user-mode scheduling.

A disadvantage over kernel only scheduling is possibly bigger latency: if all the threads in the pool are busy and you add new short task, you may wait a long time before it starts executing.

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


# Question
Title: What use are the minimum values on minimax trees?
Consider a minimax tree for an adversarial search problem. For example, in this picture (alpha-beta pruning):

When marking the the tree with $\[\min,\max\]$ values bottom-up, we first traverse node $3$ and assign $B.\max = 3$. Then we traverse $12$ and $8$ in this order, it will make sure $B.max = 3$.

But why is $B.\min = 3$? What is the use of that value?

# Answer
This figure (which is in fact correct) is used in the explanation of the alpha-beta pruning algorithm on a minimax tree. Alpha-beta pruning is a method used to prune parts of the minimax tree in an adversarial search problem. In the context of a tic-tac-toe game, minimax trees are meant to allow the computer to search through the space of all possible game boards (configurations of x's and o's) assuming the player moves are optimal. This allows the computer to come up with a move that provides the best outcome (this is why the connect-four game on your computer is so incredibly difficult to beat!). For a more complete description, I highly suggest "AI a Modern Approach" by Stuart and Norvig (pg. 162-170 ish in the 2nd ed.).

Now that we've cleared up some confusion on to the algorithm. Alpha-beta pruning tries to avoid expanding subtrees based on how the minimax algorithm works. We know that the max node at the top level will take the largest value of all its children. So, node $B$ finds the value $3$, and so far, this is the maximum value its willing to pass up to its parent so it puts this value in the MAX slot. Then it finds $12$. Remember that $B$ is a MIN node, so it wants to minimize the value it passes up to its parent, thus it keeps the value $3$ in the MAX slot. Again for $8$. When $B$ has searched all of its children, it knows the maximum lower bound ($\alpha$) solution and the minimum upper bound ($\beta$) solution of its subtree and maintains those values in MIN ($\alpha$) and MAX ($\beta$) (as \[3, 3\]).

**Note: min and max labeled in the figure are NOT the minimum and maximum values of the subtree! They are (quite confusingly labeled) the alpha-beta bounds of the solutions of the subtree (remember this is an adversarial search problem).**

Next we move to node $C$. Here we come across a $2$ in the first position. Node $C$, wanting to select the lowest value from its subtree now KNOWS that its parent will not pick its value since node $B$ found a larger value already. Therefore, we can prune the rest of the subtree and continue on to $D$.

Finally, to answer the specific question: Why is $B$.min = 3? A value for $\alpha$ (the maximum lower bound of solutions at this node) and $\beta$ (the minimum upper bound of solutions at this node) is maintained at each node in order to perform the pruning. These values bound the possible cases in which the value from a node (or its subtree) may be part of the solution.

In this example, it does not appear to play a role, however, try to look at more complicated examples (i.e. trees with a height \> 3) like this one and see if you can make sense of it.

I cannot do justice to minimax or alpha-beta pruning here (mostly because I haven't used them in years), so if you would really like to understand this please check out a book on AI like the one by Stuart and Norvig (the wikipedia page surprisingly has no visualization either).
> 7 votes

---
Tags: data-structures, trees, game-theory
---


title: Adding elements to a sorted array

text:
# Question
Title: Adding elements to a sorted array
What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)?

I was thinking something along the following lines.

I could add to the end of an array and then use bubblesort as it has a best case (totally sorted array at start) that is close to this, and has linear running time (in the best case).

On the other hand, if I know that I start out with a sorted array, I can use a binary search to find out the insertion point for a given element.

My hunch is that the second way is nearly optimal, but curious to see what is out there.

How can this best be done?

# Answer
We count the number of array element reads and writes. To do bubble sort, you need $1 + 4n$ accesses (the initial write to the end, then, in the worst case, two reads and two writes to do $n$ swaps). To do the binary search, we need $2\log n + 2n + 1$ ($2\log n$ for binary search, then, in the worst case, $2n$ to shift the array elements to the right, then 1 to write the array element to its proper position).

So both methods have the same complexity for array implementations, but the binary search method requires fewer array accesses in the long run... asymptotically, half as many. There are other factors at play, naturally.

Actually, you could use better implementations and only count actual array accesses (not accesses to the element to be inserted). You could do $2n + 1$ for bubble sort, and $\log n + 2n + 1$ for binary search... so if register/cache access is cheap and array access is expensive, searching from the end and shifting along the way (smarter bubble sort for insertion) could be better, though not asymptotically so.

A better solution might involve using a different data structure. Arrays give you O(1) accesses (random access), but insertions and deletions might cost. A hash table could have O(1) insertions & deletions, accesses would cost. Other options include BSTs and heaps, etc. It could be worth considering your application's usage needs for insertion, deletion and access, and choose a more specialized structure.

Note also that if you want to add $m$ elements to a sorted array of $n$ elements, a good idea might be to efficiently sort the $m$ items, then merge the two arrays; also, sorted arrays can be built efficiently using e.g. heaps (heap sort).
> 27 votes

# Answer
If you have any reason for not using heap, consider using Insertion Sort instead of Bubble Sort. It's better when you have a few unsorted elements.
> 10 votes

# Answer
Because you are using an array, it costs $O(n)$ to insert an item - when you add something to the middle of an array, for example, you have to shift all of the elements after it by one so that the array remains sorted.

The fastest way to find out where to put the item is like you mentioned, a binary search, which is $O(\lg n)$, so the total complexity is going to be $O(n + \lg n)$, which is on the order of $O(n)$.

That being said, if I felt particularly snarky, I could argue that you can "add to a sorted array" in $O(1)$, simply by slapping it to the end of the array, since the description doesn't indicate that the array has to remain sorted after inserting the new element.

Anyway, I don't see any reason to pull bubble sort out for this problem.
> 8 votes

# Answer
Patrick87 explained this all very well. But one additional optimization you could make would be to use something like a circular buffer: you can move items right of the position of the inserted element to the right, as usual. But you can also move items to the left of the correct position to the left. To do this, you need to treat the array as circular, i.e. the last item is right before the first one and it also requires you to keep the index where the items currently start.

If you do this, it could mean you make about half as many array accesses (assuming uniform distribution of indexes you insert to). In the case of doing binary search to find the position, it's trivial to choose whether to shift to the left or to the right. In the case of bubble sort, you need to “guess” correctly before starting. But doing that is simple: just compare the inserted item with the median of the array, which can be done in single array access.
> 5 votes

# Answer
I have used the Insertion sort algorithm effectively for this issue. At one time we had a performance issue with a hash table object, I wrote a new object that used binary search instead that increased performance significantly. To keep the list sorted it would keep track of the number of items added since the last sort (i.e. number of unsorted items,) when the list needed to be sorted due to a search request, it performed an insertion sort or a quick sort depending on the percentage of items unsorted. Use of the insertion sort was key in improving the performance.
> 5 votes

---
Tags: algorithms, efficiency, arrays, sorting
---


# Question
Title: When did commercial Speech Recognition first begin using grammar (sentence structure) for prediction?
It seems as though modern speech recognition (e.g., through Android, iOS phones) make use of grammar or sentence structure. (e.g., it might have a tough time distinguishing between "grammar" and "grandma" but can distinguish between "I'm going to see grandma" and "I'm reading a book on english grammar". (yes, I just tried it with my Android phone with vLingo app)

That is much improved (with Speaker Independent SR (i.e., no training)) over what I experienced with Dragon Dictate even using Speaker Dependent SR (with 30m of training).

So, I'm wondering whether my guess is right: When did the commercially available SR software start using grammar and sentence structure to "guess" the right speech?

# Answer
As far as I know, much of the speech recognition software is build using Hidden Markov Models (HMM) where observations are individual sound phonemes, and the states correspond to words (or some partitions of the words).

I don't think the systems take into account grammar or sentence structure in the sense that they encode rules of English so much as they naturally pick up common structure from training. Because inferring the state in an HMM is based on both the observation (the sound) and the previous state, by adding more training sequences it is possible to capture typical phrases.

For example, there are likely several instances in the training data where the word "English" is followed by the word "grammar", whereas there are very few where it is followed by "grandma", thus the dynamic aspect of the model will capture these connections naturally.
> 5 votes

# Answer
There is a pretty good description of the technology that Vlingo is using for speech rec here. They are using Hierarchical Language Models (HLMs) which does look at the context of words with in an utterance to achieve better accuracy. Alas, after being sued by Nuance for patent infringements, Vlingo has been acquired by Nuance. Soon Nuance will have a monopoly on all commercial speech recognition technology.
> 0 votes

---
Tags: natural-language-processing, history
---


# Question
Title: Optimal algorithm for finding the girth of a sparse graph?
I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.

I thought about some modification on Tarjan's algorithm for undirected graphs, but I didn't find good results. Actually I thought that if I could find a 2-connected components in $O(|V|)$, then I can find the girth, by some sort of induction which can be achieved from the first part. I may be on the wrong track, though. Any algorithm asymptotically better than $\Theta(|V|^2)$ (i.e. $o(|V|^2)$) is welcome.

# Answer
See Optimal algorithm for finding the girth of a sparse graph from cstheory.SE which has an accepted answer.
> 7 votes

---
Tags: algorithms, time-complexity, graphs
---


# Question
Title: How to implement the details of shotgun hill climbing to make it effective?
I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a *shotgun* (or *random-restart*) hill climbing algorithmic idea seems to be the best fit, as I have no clue how the best start value can be found.

But there is not a lot of information about this type of algorithm except the rudimentary idea behind it:

> \[Shotgun\] hill climbing is a meta-algorithm built on top of the hill climbing algorithm. It iteratively does hill-climbing, each time with a random initial condition $x\_0$. The best $x\_m$ is kept: if a new run of hill climbing produces a better $x\_m$ than the stored state, it replaces the stored state.

If I understand this correctly, this means something like this (assuming maximisation):

```
x = -infinity;
for ( i = 1 .. N ) {
  x = max(x, hill_climbing(random_solution()));
}
return x;

```

But how can you make this really effective, that is better than normal hill climbing? It is hard to believe that using random start values helps a lot, especially for huge search spaces. More precisely, I wonder:

* Is there a good strategy for choosing the $x\_0$ (that is implementing `random_solution`), in particular knowing (intermediate) results of former iterations?
* How to choose $N$, that is how many iterations are needed to be quite certain that the perfect solution is not missed (by much)?

# Answer
> 10 votes
The general idea behind doing multiple climbs is to try to avoid local optima. This is the reason shotgun climbing might work better than just a plain hill climbing method.

Usually one starts with a random value. On the other hand if one can guess something better, that can be used as a initial value as well. If there is no knowledge of what a good start value should be, it makes sense to use a random one.

The suitable value for $N$ varies. Usually one has to define a stopping criterion. A suitable criterion might depend on your specific domain. For example, if for some small number of moves you don't improve your solution at all, you stop. In general, you don't know -- you are using heuristics and they give you no guarantees. You might want to even determine a suitable $N$ experimentally.

---
Tags: algorithms, optimization, heuristics
---


# Question
Title: What happens to the cache contents on a context switch?
In a multicore processor, what happens to the contents of a core's cache (say L1) when a context switch occurs on that cache?

Is the behaviour dependent on the architecture or is it a general behaviour followed by all chip manufacturers?

# Answer
> 51 votes
That depends both on the processor (not just the processor series, it can vary from model to model) and the operating systems, but there are general principles. Whether a processor is multicore has no direct impact on this aspect; the same process could be executing on multiple cores simultaneously (if it's multithreaded), and memory can be shared between processes, so cache synchronization is unavoidable regardless of what happens on a context switch.

When a processor looks up a memory location in the cache, if there is an MMU, it can use either the physical or the virtual address of that location (sometimes even a combination of both, but that's not really relevant here).

With physical addresses, it doesn't matter which process is accessing the address, the contents can be shared. So there is no need to invalidate the cache content during a context switch. If the two processes map the same physical page with different attributes, this is handled by the MMU (acting as a MPU (memory protection unit)). The downside of a physically addressed cache is that the MMU has to sit between the processor and the cache, so the cache lookup is slow. L1 caches are almost never physically addresses; higher-level caches may be.

The same virtual address can denote different memory locations in different processes. Hence, with a virtually addressed cache, the processor and the operating system must cooperate to ensure that a process will find the right memory. There are several common techniques. The context-switching code provided by the operating system can invalidate the whole cache; this is correct but very costly. Some CPU architectures have room in their cache line for an ASID (address space identifier) the hardware version of a process ID, also used by the MMU. This effectively separates cache entries from different processes, and means that two processes that map the same page will have incoherent views of the same physical page (there is usually a special ASID value indicating a shared page, but these need to be flushed if they are not mapped to the same address in all processes where they are mapped). If the operating system takes care that different processes use non-overlapping address spaces (which defeats some of the purpose of using virtual memory, but can be done sometimes), then cache lines remain valid.

Most processors that have an MMU also have a TLB. The TLB is a cache of mappings from virtual addresses to physical addresses. The TLB is consulted before lookups in physically-addressed caches, to determine the physical address quickly when possible; the processor may start the cache lookup before the TLB lookup is complete, as often candidate cache lines can be identified from the middle bits of the address, between the bits that determine the offset in a cache line and the bits that determine the page. Virtually-addressed caches bypass the TLB if there is a cache hit, although the processor may initiate the TLB lookup while it is querying the cache, in case of a miss.

The TLB itself must be managed during a context switch. If the TLB entries contain an ASID, they can remain in place; the operating system only needs to flush TLB entries if their ASID has changed meaning (e.g. because a process has exited). If the TLB entries are global, they must be invalidated when switching to a different context.

# Answer
> 13 votes
The cache is typically oblivious to a context switch. Only the sequence of memory addresses accessed determines which cache lines are replaced.

The replacement policy is usually a heuristic dependent on the manufacturer and the particular microarchitecture. The problem is that the heuristic cannot predict the future, which address and therefore cache line will be accessed next.

The heuristic can be a simple as LRU (least-recently used). But with modern CPUs the heuristics are more intricate.

Take a look at the Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3 Chapter 11 explains the memory cache and the cache control mechanisms. AMD has this in Chapter 7 of the AMD64 Architecture Programmer’s Manual Volume 2: System programming. For ARM based CPUs it seems that the PDFs are only available to registered customers.

---
Tags: computer-architecture, operating-systems, cpu-cache
---


# Question
Title: Equivalence of Büchi automata and linear $\mu$-calculus
It's a known fact that every LTL formula can be expressed by a Büchi $\omega$-automaton. But, apparently, Büchi automata are a more powerful, expressive model. I've heard somewhere that Büchi automata are equivalent to linear-time $\mu$-calculus (that is, $\mu$-calculus with usual fixpoints and only one temporal operator: $\mathbf{X}$).

Is there an algorithm (constructive proof) of this equality?

# Answer
The constructive equivalence of linear-time fixed point formulae (the logic is called $\nu$TL by some) and Buechi automata is given in a paper by Mads Dam from 1992.

> Fixed Points of Buchi Automata, FST&TCS 1992.

See page 4 for the construction of a $\nu$TL formula from a Buechi automaton. The construction of a Buechi automaton from a $\nu$TL formula is more complicated and takes the rest of the paper.

The rest of this reply is a brief argument that this result existed in the literature in far less direct form. Pierre Wolper showed that there were omega-regular properties that were not LTL-definable and gave an extension of LTL (called ETL) that could express omega-regular properties.

> Temporal Logic can be more expressive, Pierre Wolper, Information and Computation, 1983.

It is also known that one can translate ETL formulae into $\nu$TL formulae, so by combining these results you can read off a translation of Buechi automata into $\nu$TL. In the other direction, it follows from the work of Buechi that S1S (the second order theory of one successor) formulae can be compiled into Buechi automata and by translating $\nu$TL formulae into S1S, we obtain a translation of $\nu$TL to Buechi automata. If you want a more in-depth introduction to these topics, I suggest Mads Dam's lecture notes, or the work of Roope Kaivola (sadly not as widely known as much related work).

> Temporal Logics, Automata, and Classical Theories - An Introduction, Mads Dam, ESSLLI 1994.
>
> Using Automata to Characterise Fixed Point Temporal Logics, Roope Kaivola
> 18 votes

# Answer
IIRC, there was a similar problem in Moshe Vardi's talk at the Fields Institute (it wasn't about $\mu$-calculus though).

You may want to check the slides or check Vardi's papers. There is definitely an algorithm but IIRC the negations cause a huge increase in the time required to perform the translation.
> 3 votes

---
Tags: logic, automata, formal-methods, linear-temporal-logic, buchi-automata
---


# Question
Title: Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?
I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i \< j \< k$ and $A\[i\] \< A\[j\] \< A\[k\]$ (or finds that there is no such triple) in linear time.

This is not a homework question; I saw it on a programming forum framed as “try to implement such an algorithm.” I suspect that it is impossible after various experiments. My intuition tells me so, but that does not really count for anything.

I would like to prove it formally. How do you do it? I would ideally like to see a proof laid out step-by-step, and then if you are so inclined, some explanation of how to go about proving/disproving simple questions like this in general. If it helps, some examples:

```
[1,5,2,0,3] → (1,2,3)
[5,6,1,2,3] → (1,2,3)
[1,5,2,3] → (1,2,3)
[5,6,1,2,7] → (1,2,7)
[5,6,1,2,7,8] → (1,2,7)
[1,2,999,3] → (1,2,999)
[999,1,2,3] → (1,2,3)
[11,12,8,9,5,6,3,4,1,2,3] → (1,2,3)
[1,5,2,0,-5,-2,-1] → (-5,-2,-1)

```

I supposed that one could iterate over $A$, and each time there is an $i \< j$ (our current $j$, that is), we make a new triple and push it onto an array. We continue stepping and comparing each triple until one of our triples is complete. So it's like `[1,5,2,0,-5,-2,-1] → 1..2.. -5.. -2.. -1`, `[1,5,2,0,-5,-2,3,-1] → 1..2.. -5.. -2.. 3`! But I think this is more complex than mere $\mathcal{O}(n)$ as the number of triples on our triple array would in the worst case correspond to the size of the input list.

# Answer
This is variation of Longest increasing subsequence problem; this is the solution presented on Wikipedia using two auxiliary arrays $M$ and $P$:

> * $M\[j\]$ — stores the position $k$ of the smallest value $A\[k\]$ such that there is an increasing subsequence of length $j$ ending at $A\[k\]$ on the range $k \leq i$ (note we have $j \leq k \leq i$ here, because $j$ represents the length of the increasing subsequence, and $k$ represents the position of its termination. Obviously, we can never have an increasing subsequence of length $13$ ending at position $11$. $k \leq i$ by definition).
> * $P\[k\]$ — stores the position of the predecessor of $A\[k\]$ in the longest increasing subsequence ending at $A\[k\]$.
>
> In addition the algorithm stores a variable $L$ representing the length of the longest increasing subsequence found so far.

This algorithm runs in worst-case time $\Theta(n\log n)$. Your problem is a special case that allows you to return when $L=3$ which pushes runtime down to $O(n)$ because the binary search runs only on arrays of length at most two, which is therefore in time $O(1)$ as opposed to $\Theta(\log n)$ in the general case.

Consider the modified pseudo code:

```
 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)
   if L==3 : return true; // you can break here, and return true.
return false; // because L is smaller than 3.

```
> 14 votes

# Answer
### A note on methodology

I thought a bit about this problem, and came to a solution. When I read Saeed Amiri's answer, I realized that what I came up with was a specialized version of the standard longest subsequence finding algorithm for a sequence of length 3. I'm posting the way I came up with the solution, because I think it is an interesting example of problem solving.

### The two-element version

Let's start small: instead of looking for three indices at which the elements are in order, let's look for two: $i \< j$ such that $A\[i\] \< A\[j\]$.

If $A$ is decreasing (i.e. $\forall i \< j, A\[i\] \ge A\[j\]$, or equivalently $\forall i, A\[i\] \ge A\[i+1\]$), then there are no such indices. Otherwise, there is an index $i$ such that $A\[i\] \< A\[i+1\]$.

This case is very simple; we'll try to generalize it. It shows that the problem as stated is not solvable: the requested indices do not always exist. So we will rather ask that the algorithm either returns valid indices, if they exist, or correctly claims that no such indices exist.

### Coming up with the algorithm

I will use the term *subsequence* to mean an extract from the array $A$ consisting of indices that may not be consecutive ($(A\[i\_1\],\ldots,A\[i\_m\])$ with $i\_1 \< \dots \< i\_m$), and *run* to mean consecutive elements of $A$ ($(A\[i\],A\[i+1\],\ldots,A\[i+m-1\])$).

We just saw that the requested indices do not always exist. Our strategy shall be to study when the indices do not exist. We'll do this by supposing we're attempting to find the indices and seeing how our search might go wrong. Then the cases where the search doesn't go wrong will provide an algorithm to find the indices.

With two indices, we could find consecutive indices. With three indices, we might not be able to come up with $j=i+1$ and $k=j+1$. However, we can consider the case when there is a run of three strictly increasing elements ($A\[i\] \< A\[i+1\] \< A\[i+2\]$) to be solved, as it is easy to recognize such runs, and see how this condition might not be met. Suppose that the sequence has no strictly increasing run of length 3.

The sequence only has strictly increasing runs of length 2 (which I'll call *ordered pairs* for short), separated by a decreasing run of length at least 2. In order for a strictly increasing run $A\[j\] \< A\[j+1\]$ to be part of an increasing 3-element sequence, there must be an earlier element $i$ such that $A\[i\] \< A\[j\]$ or a later element $k$ such that $A\[j+1\] \< A\[k\]$.

A case when neither $i$ nor $k$ exists is when each ordered pair is entirely lower than the next one. This isn't all: when the pairs are interlaced, we need to compare them more finely.

The leftmost element $i$ of an increasing subsequence needs to come early and be small. The next element $j$ needs to be larger, but as small as possible to be able to find a third larger element $k$. The first element $i$ is not always the smallest element in the sequence, and it is not always the first for which there is a subsequent larger element, either — sometimes there is a lower 2-element subsequence further on, and sometimes there is a better fit for the already-found minimum.

Going from left to right, we tentatively pick the smallest element as $i$. If we find a larger element further right, we pick this pair as a tentative $(i,j)$. If we find an even larger $k$, we've won. The key thing to note is that our pick of $i$ and our pick of $(i,j)$ are updated independently: if we have a candidate $(i,j)$ and we find $i' \> j$ such that $A\[i'\] \< A\[i\]$, $i'$ becomes the next candidate $i$ but $(i,j)$ remains. Only if we find $j'$ such that $A\[j'\] \< A\[j\]$ will $(i',j')$ become the new candidate pair.

### Statement of the algorithm

Given in Python syntax, but beware that I haven't tested it.

```
def subsequence3(A):
    """Return the indices of a subsequence of length 3, or None if there is none."""
    index1 = None; value1 = None
    index2 = None; value2 = None
    for i in range(0,len(A)):
        if index1 == None or A[i] < value1:
            index1 = i; value1 = A[i]
        else if A[i] == value1: pass
        else if index2 == None:
            index2 = (index1, i); value2 = (value1, A[i])
        else if A[i] < value2[1]:
            index2[1] = i; value2[1] = A[i]
        else if A[i] > value2[1]:
            return (index2[0], index2[1], i)
    return None

```

### Proof sketch

`index1` is the index of the minimum of the part of the array that has already been traversed (if it occurs several times, we retain the first occurrence), or `None` before processing the first element. `index2` stores the indices of the increasing subsequence of length 2 in the already-traversed part of the array that has the lowest largest element, or `None` if such a sequence doesn't exist.

When `return (index2[0], index2[1], i)` runs, we have `value2[0] < value[1]` (this is an invariant of `value2`) and `value[1] < A[i]` (obvious from the context). If the loop ends without invoking the early return, either `value1 == None`, in which case there is no increasing subsequence of length 2 let alone 3, or `value1` contains the increasing subsequence of length 2 that has the lowest largest element. In the latter case, we furthermore have the invariant that no increasing subsequence of length 3 ends earlier than `value1`; therefore the last element of any such subsequence, added to `value2`, would form an increasing subsequence of length 3: as we also have the invariant that `value2` is not part of an increasing subsequence of length 3 contained in the already-traversed part of the array, there is no such subsequence in the whole array.

Proving the aforementioned invariants is left as an exercise for the reader.

### Complexity

We use $O(1)$ additional memory, and traverse the array as a stream from left to right. We perform $O(1)$ processing for each element, leading to a run time of $O(n)$.

### Formal proof

Left as an exercise to the reader.
> 11 votes

# Answer
There is an $O(n)$ time algorithm, which uses $O(n)$ space.

First, traverse the array left to right maintaining a stack and an auxiliary array which tells you for each element, the index of an element greater than it and to the right of it.

Initially the stack is empty and the aux array contains all $-1$s.

Each time you consider a new element in the array, if that element is greater than the top element of the stack, you pop it off the stack, and set the aux array element corresponding to the top to have the index of the new element under consideration.

Continue popping elements off the stack and setting the corresponding index, while the current element is greater. Once the top has an element which is not lesser (or becomes empty), push the current element onto the stack, and proceed to the next element of the array, repeating the above step.

Make another pass (and another aux array), but going right to left.

Make a pass through the aux arrays and pick a position where both the corresponding entries in the array are not $-1$.

Since you consider each element of the array only a constant number of times, this is $O(n)$ time.

I believe you can also get rid of the stacks (by considering "suffix maximums" and "prefix minimums"), but the stacks give you the closest elements. So if you wanted to minimize say $k-i$, you could use the stacks.

Pseudo code for the first pass might look like this:

```
Stack <Pair<Elem, Index>> greats;
Elem auxArr[inputArr.Length];

for (Index i = 0; i < inputArr.Length; i++) {

    while (!greats.IsEmpty() && inputArr[i] > greats.PeekTop().Elem) {
        Pair top = greats.Pop();
        auxArr[top.Index] = i;
    }

    Pair p;
    p.Elem = inputArr[i];
    p.Index = i;

    greats.Push(p);
}

```
> 8 votes

---
Tags: algorithms, arrays, subsequences
---


# Question
Title: Choosing taps for Linear Feedback Shift Register
I am confused about how taps are chosen for Linear Feedback Shift Registers.

I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, R3, R2, R1$ and $R0$ and the taps come out of $R0$ and $R3$.

How are these taps decided? When I am given a connection polynomial but no diagram, how do I know what values I should XOR?

# Answer
> 10 votes
The taps are decided by the polynomial in a straightforward way: for $X^n$, you connect the $n$th tap. Note that in your diagram the *first* tap is $R4$, the 2nd is $R3$ etc..

Since your polynomial is $X^5+X^2+1$ the feedback is an XOR of the output of the 2nd tap ($R3$) and the 5th tap ($R0$). The "$+1$" of the polynomial ($X^0$) is usually always there and corresponds to the "feedback" itself, i.e., the line connected into the first bit ($R4$).

The output should be the "feedback" line (rather than $R0$). This is important since the polynomial is identified with the generated sequence, and if you take the output of $R0$ you generate a different sequence, not the one identified with $X^5+X^2+1$ (although they are the same up to a prefix)

See more details in Wikipedia: Linear feedback shift register.

---
Tags: cryptography, pseudo-random-generators, shift-register
---


title: Subset-sum and 3SAT

text:
# Question
Title: Subset-sum and 3SAT
Two things (this may be naive):

1. Does anyone believe there is a sub-exponential time algorithm for the Subset-sum problem? It seems obvious to me that you would have to look through all possible subsets to prove (the negation of) an existential statement. It seems obvious in the same way that if somebody asked you "Is $x$ in this list of $n$ numbers?", it's obvious that you would have to look through all $n$ numbers.
2. If Subset-sum can be polynomial time reduced to 3SAT and we agree on (1), then doesn't that mean $NP \neq P$?

# Answer
> 6 votes
There *is* an algorithm for subset-sum that runs faster than $O(2^n)$! That is, it is faster than examining all possible subsets. This proves that your intuition is wrong. Wikipedia has a nice writeup of this algorithm.

> If Subset-sum can be polynomial time reduced to 3SAT and we agree on (1), then doesn't that mean $NP \neq P$?

If someone *proves* (1) (the above algorithm is still exponential), then yes, $P \neq NP$. However, if all humans on earth would somehow 'agree' that (1) is true, then that is not enough to make $P \neq NP$ proven - just to address your specific usage of the word 'agree'.

# Answer
> 3 votes
> Does anyone believe there is a sub-exponential time algorithm for subset-sum?

I'm sure there's someone somewhere who believes it, but the vast majority of computer scientists believe that there is no such algorithm. However no one has proved this yet.

> It seems obvious to me that you would have to look through all possible subsets to prove the negation of an existential statement.

This is not generally true. There are a lot of problems of the form "Does there exist a subset of a given set for which some property is true" that can be solved without looking at all subsets.

> If subset-sum can be polynomial time reduced to 3SAT and we agree on (1), then doesn't that mean NP =/= P?

Yes, if someone proves that it is not possible to solve subset-sum in polynomial time, that also proves that $NP \neq P$.

# Answer
> 1 votes
It is a bit strange that you are talking about reducing SUBSET-SUM to 3SAT to conclude $P \neq NP$ from the hypothesis of non-existence of a sub-exponential algorithm for SUBSET-SUM.

The fact that SUBSET-SUM is in $NP$, coupled with the hypothesis that it has no polynomial time algorithms is enough to show that $P \neq NP$. There is no need to talk about any reductions, or even pick problems which are $NP$-Complete.

So let us try to re-interpret your problem to what I think you might be asking:

> Suppose problem $A$ can be reduced to problem $B$ in polynomial time. Does the non-existence of a sub-exponential time algorithm ( $o(c^n)$ for every $c \gt 1$, note: smallOh) for $A$ imply the non-existence of a sub-exponential time algorithm for $B$?

The answer is not necessarily.

This is because the polynomial time algorithm for reduction can blow up the size of your input!

Suppose every reduction from $A$ to $B$ changed the input size from $n$ to $n^3$.

Now any $\Theta(2^{\sqrt{k}})$ time algorithm for $B$ (with input size $k$) will solve $A$ (with input size $n$) in $\Theta(2^{n^{3/2}})$ time, and does not contradict the non-existence of a sub-exponential time algorithm for $A$.

See also this question on cstheory.SE.

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


# Question
Title: Is it viable to use an HMM to evaluate how well a catalogue is used?
I was interested on evaluating a catalogue that students would be using to observe how is it being used probabilistically.

The catalogue works by choosing cells in a temporal sequence, so for example:

* Student A has: ($t\_1$,$Cell\_3$),($t\_2$,$Cell\_4$)
* Student B has: $(t\_1,Cell\_5),(t\_2,Cell\_3),(t\_3,Cell\_7)$.

Assume that the cells of the table are states of a Hidden Markov Model, so the transition between states would map in the real world to a student going from a given cell to another.

Assuming that the catalogue is nothing more than guidance, it is expected to have a certain kind of phenomenon to occur on a given artifact. Consider this artifact to be unique, say, for example a program.

What happens to this program is a finite list of observations, thus, for a given cell we have a finite list of observations for following the suggestion mentioned on that cell. On a HMM this would be then the probability associated to a state to generate a given observation in this artifact.

Finally, consider the catalogue to be structured in a way that initially it is expected that the probability to start in a given cell is equal. The catalogue does not suggest any starting point.

* **Question 1**: Is the mapping between the catalogue and the HMM appropriate?
* **Question 2**: Assuming question 1 holds true. Consider now that we train the HMM using as entries $(t\_1,Cell\_1), (t\_2,Cell\_3) , ... (t\_n,Cell\_n)$ for the students. Would the trained HMM, once asked to generate the transition between states that it is most likely yields as result what is the most used way by the people who used the catalogue for a given experiment $\epsilon$?

# Answer
**Ad Question 1:** Assuming that your assumptions on how the catalogue is used -- that is the choice of the next cell only depends on the current (or constantly many preceeding) cell(s), *not* the (full) history -- then yes, you can use a Markov Chain to model it.

However, you do not seem to need the "Hidden" part; this is only useful if you have (probabilistic) output in the states which you observe. In contrast, you want to observe the students' cell states directly.

Imagine you can not observe which cells students are in but only how much they like the current cell; this could be implemented by notorious "Was this useful to you?" buttons; in general, assume every students gives feedback from $\\{1, \dots, k\\}$ in every cell but you do not know which cell they are in. Then you can use a HMM to estimate their cell sequence given their feedback sequence.

**Ad Question 2:** Let me illustrate the use continuing above train of thought. For $n=k=3$, we have the following Markov chain:

\[source\]

$p\_{i,j}$ is the probability to transition from state $i$ to state $j$; note that $p\_{i,0}=0$ for all $i$ and those edges have been left out¹. Let $p\_{i,\bot}$ the probability of terminating in state $i$ (we leave out another dummy state for clarity). $q\_{i,l}$ is the probability to emit $l$ when entering (or, equivalently, leaving) state $i$; this models our feedback. Of course, we require $\sum\_j p\_{i,j} + p\_{i,\bot} = \sum\_l q\_{i,l} = 1$ for all $i$.

Note that the state sequence $0,1,2$ has probability $p\_{0,1} \cdot p\_{1,2}$ -- that is a central property of Markov chains. The output sequence $1,2$, on the other hand, has probability $q\_{0,1}\cdot p\_{0,1}\cdot q\_{1,2} + q\_{0,1}\cdot p\_{0,2}\cdot q\_{2,2} + q\_{0,1}\cdot p\_{0,3}\cdot q\_{3,2}$.

In a real world scenario, we would have to *train* our Markov chain. Let us assume we have some sequences of both state and output²:

$\qquad \begin{align} &(0,1), (1,1), (2,1), (3,1) \\ &(0,2), (1,3), (3,1) \\ &(0,1), (3,3), (1,2) \end{align}$

Now we just count how often each transition and output happened and set our probabilities to the relative frequencies³:

\[source\]

Now you can do the interesting stuff. Ignoring the output, you can determine the path with highest probability, you can determine the output sequence with highest probability but most importantly, and here the *hidden* part comes into play, you can find the most likely state sequence given an output sequence with Viterbi algorithm.

**Bottom line:** yes, you can use Markov chains resp. hidden Markov models (depending on your needs) to model your scenario. Wether the fundamental assumption -- the probability for the next cell only depends on the current cell -- makes sense is another question entirely.

---

1. We need a starting state, but we can make it a dummy by never going back. We can ignore its output or introduce a dummy output that is only and always emitted in state $0$.
2. If we have only output sequences, we can use the forward-backward algorithm.
3. Due to our low number of observations, we have a number of impossible transitions/emissions. Usually you assume that everything is possible and has just not been observed due to low probability. We can compensate for this by adding $1$ to all counts; this way, all sequences have probability $\gt 0$.
> 5 votes

---
Tags: probability-theory, empirical-research, modelling, hidden-markov-models
---


# Question
Title: Finding a 5-Pointed Star in polynomial time
**I want to establish that this is part of my homework for a course I am currently taking. I am looking for some assistance in proceeding, NOT AN ANSWER.**

This is the question in question:

> A 5-pointed-star in an undirected graph is a 5-clique. Show that 5-POINTED-STAR $\in P$, where 5-POINTED-STAR = $\\{ \<G\>$ $: G$ contains a 5-pointed-star as a subgraph $\\}$.

Where a clique is CLIQUE = $\\{(G, k) : G$ is an undirected graph $G$ with a $k$-clique $\\}$.

Now my problem is that this appears to be solving the CLIQUE problem, determining whether a graph contains a clique with the additional constraint of having to determine that the CLIQUE forms a 5-pointed star. This seems to involve some geometric calculation based on knowledge of a 5-pointed star. However, in Michael Sipser's *Theory of Computation*, pg 268, there is a proof showing that CLIQUE is in $NP$ and on page 270 notes that,

> *We have presented examples of languages, such as HAMPATH and CLIQUE, **that are members of NP but that are not known to be in $P$.*** \[emphasis added\]

If CLIQUE is not in $P$, why five pointed star be in $P$? Is there something I'm not seeing? **Remember, this is a HOMEWORK PROBLEM and A DIRECT ANSWER WOULD NOT BE APPRECIATED.** Thanks!

# Answer
> 11 votes
If $G=(V,E)$ is a graph, how many subsets of $V$ of size $5$ exist?

If there is a 5-clique, one of this subsets is a clique.

Spoilers below:

> There are ${|V| \choose 5}$ possible subsets to check, that is, at most $|V|^5$ options, which is polynomial in the input. **This is NOT the case** for an arbitrary $k$, since $|V|^k$ might be exponential in the input, and this is why $\text{CLIQUE} \notin P$ (unless P=NP, agghh.).

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


# Question
Title: What is the difference between "Decision" and "Verification" in complexity theory?
In Michael Sipser's *Theory of Computation* on page 270 he writes:

> P = the class of languages for which membership can be decided quickly.
> NP = the class of languages for which membership can be verified quickly.

What is the difference between "decided" and "verified"?

# Answer
> 12 votes
The task of *deciding* membership is: given any input $x$, decide wether $x \in L$, i.e. compute the following function:

$\qquad \displaystyle \chi\_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

On the other hand, the task of *verifying* membership is: given any input $x$ and a (proposed) *proof* (or *witness*) of membership, check quickly wether $x\in L$ *by that proof*¹.

For example, consider prime factorisation. Given $n \in \mathbb{N}$, compute all prime factors of $n$. On the other hand, given $(n, \\{i\_1, \dots, i\_k\\})$, verify that $\prod\_{j=1}^k i\_j = n$. Which is easier?

Another example: Given a weighted graph $G = (V,E)$, decide wether there is a Hamilton circle (that visits all nodes) with weight at most $k$. On the other hand, given $(G, (v\_1, \dots, v\_n))$, verify wether the path $v\_1 \to \dots \to v\_n$ visits all nodes exactly once and has weight at most $k$. Which is harder?

---

1. So you will say "no" if $x \in L$ but the proof is wrong. That is fine, though, as we consider nondeterministic machines in this context; it is only important that we can *guess* the correct proof and verify it (quickly).

# Answer
> 8 votes
If we ignore efficiency issues, there is another example that illustrates the difference by analogy. We know that the halting problem is not decidable: given a code $e$ for a Turing machine, there is no effective way to determine whether the machine stops if it is run with no input.

But if a machine *does* halt, it is not hard to prove to someone else: just tell them how many steps the machine runs before it stops. They can run the machine for that many steps and know if you told the truth (ignoring efficiency, of course).

So the set of halting Turing machines is not decidable, but it is verifiable. Note that no proof has to be given for machines that *don't* halt. Verification is asymmetric in the sense that only membership *in* the set has the be verifiable, membership *out* of the set does not.

The situation with P and NP is analogous. A language is in NP if there is a system of proofs such that each object that is *in* the language has a short proof (bounded by a polynomial in the size of the object) that can be verified efficiently (with a number of steps bounded by a polynomial in the size of the input).

On the other hand, a language is in P if there is a way to tell whether an arbitrary object is or is not in the language using a number of steps bounded by a polynomial in the size of the object. Now we have to worry about arbitrary inputs, not just objects in the language. But this problem is symmetric: if a language is in P then so is its complement. The question whether the complement of every NP language is also an NP language is unsolved.

(This analogy mught suggest that NP problems are to P problems like r.e. sets are to computable sets. That is somewhat true, but it can be misleading. It is a basic fact that a set that is r.e. and co-r.e. is computable, while it is not known whether every set that is NP and Co-NP is in P).

---
Tags: complexity-theory, terminology, decision-problem
---