# Question
Title: Is it decidable whether a TM reaches some position on the tape?
I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$.

> For an integer $c\>1$, and the following three problems:
>
> 1. Is it true that for every input $x$, M does not pass the $|x|+c$ position when running on $x$?
> 2. Is it true that for every input $x$, M does not pass the $\max \\{|x|-c,1 \\}$ position when running on $x$?
> 3. Is it true that for every input $x$, M does not pass the $(|x|+1)/c$ position when running on $x$?
>
> How many problems are decidable?

Problem number (1), in my opinion, is in $\text {coRE} \smallsetminus \text R$ if I understand correct since, I can run all inputs in parallel, and stop if some input reached this position and for showing that it's not in $\text R$ I can reduce the complement of **Atm** to it. I construct a Turing machine $M'$ as follows: for an input $y$ I check if $y$ is a history of computation, if it is, then $M'$ running right and doesn't stop, if it's not, then it stops.

For (3), I believe that it is decidable since for $c \geqslant 2$ it is all the Turing machines that always stay on the first cell of the stripe, since for a string of one char it can pass the first cell, so I need to simulate all the strings of length 1 for $|Q|+1$ steps (Is this correct?), and see if I'm using only the first cell in all of them.

I don't really know what to do with (2).

# Answer
> 12 votes
Any situation which asks whether a Turing Machine is confined to a finite section of the tape (say of length $n$) on a given input is decidable.

The argument works as follows. Consider the Turing Machine, the tape, and the position of the Turing Machine on the tape. All together these have a finite number of configurations. To be specific, there are only $t = n|\Gamma|^n|Q|$ possible configurations. $\Gamma$ is the set of tape symbols and $Q$ is the set of states. I'll continue to use the word "configuration" to describe the state of the Turing Machine combined with the state of the tape and its position on the tape for the remainder of this answer, but that is not standard vocabulary.

Run the machine, keeping track of all its past configurations. If it ever goes beyond point $n$, return "yes, $M$ passes position $n$". Otherwise, the machine is somewhere between 0 and $n$. If the machine ever repeats a configuration--its state, the symbols on the tape, and its position on the tape are identical to what they were before--return "no, $M$ never passes position $n$."

By the pidgeonhole principle, this has to happen in no more than $t+1$ steps. So all of the above is decidable; after at most $t+1$ simulated steps you get an answer.

A quick note on why this works: when the machine, the tape, and its position on the tape repeat themselves, there must have been a sequence of configurations between these repetitions. This sequence will happen again, leading to the same configuration one more time--the machine is in an infinite loop. This is because we're keeping track of every aspect of the Turing Machine; nothing outside of the configuration can have an impact on what happened. So when a configuration repeats, it will repeat again, with an identical series of configurations in between.

So confining the tape to a finite part of the string is decidable. Therefore, by iterating over all possible input strings, the problem is in $\text{coRE}$ for all three questions. You may have already realized this (between your ideas for 1 and 3 and Ran G's answer for 2 it seems solved completely anyway) but I figured it may be worth posting nonetheless.

# Answer
> 4 votes
(2) is very similar to (3) and the same reasoning you had for (3) applies here as well: note that machines that in $L\_2$ have a strange property - they don't read the entire input (they never reach it's last $c$ bits.) And this is true for *every* input.

Ok, so now let's consider only inputs up to length $c$. For each one of them, there are only two options: the machine loops/halts w/o moving the head, or it moves the head. If it moves the head on some $x$ (with $|x|\le c$), that machine is not in $L\_2$ due to that input $x$. Otherwise, I claim the machine is in $L\_2$. Since it never moves the head - it has no idea what the size of the input is! this means it behaves the same for all the inputs of length $|x|\>c$. Therefore, $L\_2$ is decidable.

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


# Question
Title: Why use comparisons instead of runtime for comparing two algorithms?
I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. Why can't we compare which one is better by running both programs and counting the total time needed to run the algorithms?

# Answer
This is actually a deep issue that has some methodic and some pragmatic answers. I assume you want to know something about the *algorithm(s)* at hand. If you want to know which algorithm works better on a given machine on given inputs, go ahead and measure runtimes. If you want to compare the quality of a compiler for a given algorithm, go ahead and measure runtimes. For learning something about the algorithm, don't do it.

Let me first give some reasons why using runtimes is not a good idea.

1. **Generality**
Runtimes measured using one language and one compiler on one machine have little meaning if you change any component. Even slightly different implementations of the same algorithm may perform differently because you trigger some compiler opimisation in on case but not in the other.
2. **Prediction**
So you have a couple of runtimes for some inputs. What does that tell about the runtime of some other input? In general, nothing.
3. **Significance**
Usually, you won't benchmark *all* inputs (of some size), so that immediately restricts your ability to compare algorithms: maybe your test set triggered the worst case in one and the best case in the other algorithm? Or maybe your inputs were too small to exhibit the runtime behaviour.
4. **Metering**
Measuring runtimes *well* is not trivial. Is there a JIT? Has there been contention, i.e. are you counting time the algorithm did not even run? Can you reproduce exactly the same machine state for another run (of the other algorithm), in particular concurrent processes and caches? How is memory latency dealt with?

I hope these convinced you that runtimes are a horrible measure to compare algorithms, and that some general, abstract method for investigating algorithm runtime is needed.

On to the second part of the question. Why do we use comparisons or similar elementary operations?

1. **Analytic tractability**
Assuming you want to do formal analysis, you have to be *able* to do it. Counting individual statements is very technical, sometimes even hard; some people do it nevertheless (e.g. Knuth). Counting only some statements -- those that *dominate* the runtime -- is easier. For the same reason, we often "only" investigate (upper bounds on) worst-case runtime.
2. **Dominance**
The selected operation *dominates* the runtime. That does not mean that it contributes the most runtime -- comparisons clearly do not, e.g. in Quicksort when sorting word-sized integers. But they are executed *the most often*, so by counting them you count how often the most executed parts of the algorithm are run. Consequently, your *asymptotic* runtime is proportional to the number of dominant elementary operations. This is why we are comfortable using Landau notation and the word "runtime" even though we only count comparisons.

Note that it can be useful to count more than one operation. For example, some Quicksort variants take more comparisons but less swaps than others (on average).

For what it's worth, after you have done all the theory you might want to revisit runtimes in order to verify that the predictions your theory makes are sound. If they are not, your theory is not useful (in practice) and has to be extended. Memory hierarchy is one of the first things you realise is important but missing in basic analyses.
> 14 votes

# Answer
This is because the total time to run the algorithms has a dependency on the hardware in which it is ran on along with other factors. It is not reliable to compare two algorithms if one is running on a Pentium 4 and the other running on, let's say, a Core i7. Not only this, but let's say you ran both on the same computer. What's to say that they both have the same amount of processor time? What happens if some other process has a higher priority than the process of the one of the algorithms?

To get past this, we decouple away from this overall time to complete, and instead comparing based on how well the algorithm scales. You may have noticed notation such as O(1) or O(n^2) in the research papers. This may require a bit more reading, if you are interested see Big O notation.
> 10 votes

# Answer
Since the other answers explain why we analyze runtime in terms of number of elementary operations, let me offer a couple of reasons for *why comparisons* are the right metric of many (not all) sorting algorithms:

* for many sorting algorithms the number of comparisons dominates the running time, i.e. at least as many comparisons are performed as any other elementary operation
* comparisons are the *expensive* operation; think about how a sorting routine is implemented in library: the sort function is passed an array of elements and a pointer to a function that compares two elements; in general calling and waiting for the compare function to execute is more expensive than "internal" operations; as this function is provided by the user, it's harder to optimize it
* (this may or may not be a good reason for some) we can can say something *interesting* about the number of comparisons that are sufficient and necessary to sort a sequence; we know how to do this in the worst case and on average for various distributions, even how to design an algorithm that converges to optimal as it is run on items sampled iid from an unknown distribution (Self-Improving Algorithms); we know how to do this when some comparisons are given for free (Sorting with Partial Information)
> 7 votes

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


# Question
Title: Dataflow framework for global analysis: Why meet, then apply?
In Chapter 9 of the Dragon Book, the authors describe the dataflow framework for global analysis (described also in these slides). In this framework, an analysis is defined by a set of transfer functions, along with a meet semilattice.

At each step of the iteration, the algorithm works by maintaining two values for each basic block: an IN set representing information known to be true on input to the basic block, and an OUT set representing information known to be true on output from the basic block. The algorithm works as follows:

1. Compute the meet of the OUT sets for all predecessors of the current basic block, and set that value as the IN set to the current basic block.
2. Compute $f(IN)$ for the current basic block, where $f$ is a transfer function representing the effects of the basic block. Then set OUT for this block equal to this value.

I am confused about why this algorithm works by taking the meet of all the input blocks before applying the transfer function. In some cases (non-distributive analyses), this causes a loss of precision. Wouldn't it make more sense to apply the transfer function to each of the OUT values of the predecessors of the given block, then to meet all of those values together? Or is this not sound?

Thanks!

# Answer
It's the classic precision/efficiency tradeoff. You can, in fact, move the meet outside, since $f(x \sqcap y) \sqsubseteq f(x) \sqcap f(y)$. A canonical example of where this makes a difference is in the following constraint-propagation problem:

```
IF b
  x = 1
ELSE
  x = -1

y = x*x

```

The Dragon Book's suggestion will compute $(x=1) \sqcap (x=-1)=\top$ before evaluating $x\*x$, and will thus not capture that $y$ is a constant. By computing the meet after (twice) evaluating the multiplication, yours will. What you have effectively done is added a small amount of path-sensitivity, for a small price in efficiency. You can continue down this path arbitrarily. Two steps of this analysis may compute $f(f(w\sqcap x) \sqcap f(y\sqcap z))$. Your suggestion would instead compute $f(f(w)\sqcap f(x)) \sqcap f(f(y) \sqcap f(z))$, but you can take this farther and increase the path-sensitivity by computing $f(f(w))\sqcap f(f(x))\sqcap f(f(y)) \sqcap f(f(z))$. The fully path-sensitive MOP (meet-over-paths) solution is undecidable. The Dragon Book's algorithm gives an MFP (maximal fixed point) solution, which safely approximates the MOP. You've simply refined the approximation a bit.
> 3 votes

---
Tags: compilers, program-optimization
---


# Question
Title: Is #P closed under exponentiation? modulo?
The complexity class $\newcommand{\sharpp}{\mathsf{\\#P}}\sharpp$ is defined as

$\qquad \displaystyle \sharpp = \\{f \mid \exists \text{ polynomial-time NTM } M\ \forall x.\\, f(x) = \\#\operatorname{accept}\_{M}(x)\\}$.

It is known that $\sharpp$ is closed under addition, multiplication and binomial coefficient. I was wondering if it is closed under power. For example, we are given a $\sharpp$ function $f$ and another $\sharpp$ function $g$. Is it true that $f^{g}$ or $g^{f}$ are $\sharpp$ functions as well?

This is edit after the question has been answered.

Is ($f$ modulo $g$) a $\sharpp$ function? How about when we are given a $\newcommand{\FP}{\mathsf{FP}}\FP$ function $h$. Then is ($f$ modulo $h$) a $\sharpp$ function?

# Answer
No. Take $f(n)=g(n)=2^n$ for a counterexample.
> 7 votes

---
Tags: complexity-theory, turing-machines, closure-properties
---


# Question
Title: Pizza commercial claim of 34 million combinations
A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out. Here's what I have so far: From the online ordering site I got the choices

1. crust (4 types, choose 1)
2. size (4 types, choose 1) some crusts are limited to a certain size - not accounting for that, but would like to.
3. cheese (5 types, choose 1)
4. sauce (4 types, choose 1)
5. sauce level (3 types, choose 1)
6. meats (9 types, choose up to 9)
7. non-meats (15 types, choose up to 15)

So I figured this was a combination problem (order is not important) and not an n choose k problem, null is allowed for anything but crust and crust, size, cheese, sauce and sauce level would all be choose only one. Meats and non-meats $2^?$? So that would be:

1. crust $\binom{4}{1}=4$
2. size $\binom{4}{1}=4$
3. cheese $\binom{5}{1}=5$
4. sauce $\binom{4}{1}=4$
5. sauce level $\binom{3}{1}=3$
6. meats $2^9 = 512$
7. non-meats $2^{15} = 32768$

At this point I'm stuck, how do I combine these to arrive at the total number of possible combinations?

I found this site helpful.

**ETA:** If I don't account for the limitations on crust size - some crusts are only available in certain sizes - there are over 16 billion; 16,106,127,360 combinations available, so they were off by quite a bit.

# Answer
Ok, A bit more detailed answer than in the comments.

Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$.

The interesting part are things like the non-meat options. You have 15 and can choose any set of up to 15. Mathematically, this means ${15 \choose 0} + {15 \choose 1} + \cdots + {15\choose 15}$.

As you mentioned, there is a nice formula for such sums: $$\sum\_{i=0}^n {n \choose i} = 2^i$$ thus, for the non-meat options you have $2^{15}=32768$ options, as you said. (see here for more formulas).

Lastly, to combine all the options, you just multiply them. If you have 4 possible sizes, and, say, 4 possible crusts, then you have $4\times 4=16$ different combinations overall.

So, multiplying everything you get 16.106.127.360, which is larger than 34 million.
> 19 votes

---
Tags: combinatorics, discrete-mathematics
---


# Question
Title: Subset sum, pseudo-polynomial time dynamic programming solution?
I found the P vs NP problem some time ago and I have recently worked on the subset sum problem. I have read Wikipedia article on the Subset Sum problem as well as the question Subset Sum Algorithm

I have looked at the problem and found some solutions but so far they seem to be NP, I believe I can make a sufficiently fast algorithm in NP time.

My problem is I am not good in theory so it doesn't help me much to talk about the Cook-Levin Theorem or Non-Deterministic Turing Machines.

What I would like is an explanation of the pseudo-polynomial time dynamic programming subset sum that on Wikipedia.

I have read it and I believe I understand the general concept of why it is NP instead of P (related to the size of the input rather than the operations with it), but I do not understand the algorithm.

I would appreciate if someone would put provide an example with some numbers and how it works. It would help me a lot because it would:

* Give me ideas to improve my future algorithm
* Help me understand intuitively when an algorithm is pseudo-polyonmial instead of NP.

# Answer
> 5 votes
Rephrasing Kaveh's comment as an answer:

If you bound the size the values in the input (bound the number of bits for each value to be logarithmic in the total number of bits of the input) then the problem can be solve in polynomial time using dynamic programming. If they are not bounded they can have values which are exponentially large and the size of the table for the dynamic programming would be exponential.

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Methods to evaluate a system of written rules
I was trying to come up with a system that would evaluate bylaws for an organization as to determine their underlying logic.

I think a first-order predicate system would work for representing the rules, which could be translated from the text via part-of-speech tagging and other NLP techniques.

Is there a systematic way to interpret the first-order logic rules as a whole, or some type of ML architecture that would work as a second layer to find similarities between the elements.

For example,

> List of fun activities:
>
> * golf
> * coffee break
> * pizza
>
> Bylaws:
>
> 1. On Friday, we play golf
> 2. On Friday or Saturday, we take a quick coffee break, and if it's Saturday, we get pizza

Conclusion: our group has fun on weekends

It sounds far fetched, but I'm curious if it's possible. I also realize that perhaps more first-order logic would be a better fit for driving the conclusions of the second layer.

# Answer
The trick here is that this works well provided that your rules can be expressed in predicate form. Is golf still fun if it's raining, or if you play poorly?

If you need something more flexible, you might want to look at some statistical/Baysean tools. There, you'd say that golf had a high probability of being fun, not that it was always fun all the time ever.
> 2 votes

---
Tags: machine-learning, algorithms, pattern-recognition, logic
---


# Question
Title: Dynamic changes to classes or context activation -- how to treat existing objects in a consistent way?
I am looking for references and papers on the following topic.

1. In *general*, some programming languages allow dynamic changes to classes. As an example, a new instance variable ‘weight’ can be added to the class `Edge` (the class of unweighted edges of graphs). But what should happen with existing edge objects?

They can be upgraded to include the new instance variable with a default value, perhaps weight `0`, in the edge example. Or existing objects stay the same.
2. In *context-oriented* programming, similar situations can arise, when a context is dynamically activated at run-time. This may affect changes to methods which are currently executed (although I am concerned at the single thread execution at the moment).
3. Considering *design patterns*, when a proxy object wraps another object, references to the old object may expect certain invariants that the proxy object doesn’t adhere to. This may also lead to inconsistencies when an object is wrapped/’updated’ with a proxy object.

Are there any references that list possible ways to treat the problem in case of dynamic changes/activation? Like the options to keep the state consistent?

I looked primarily in the communities of dynamic software evolution, context-oriented programming and software components. Are there other important communities I can search to find references?

# Answer
A recent paper on this topic that I stumbled upon is Incremental Dynamic Updates with First-class Contexts by Erwann Wernli, Mircea Lungu, and Oscar Nierstrasz. The approach taken in the paper is not based on global updates. Rather, multiple versions of a system run simultaneously in what is called a *context*. Objects are gradually migrated from one context to another, at which time an update is performed. Bidirectional transformations are used to maintain consistency between old an new contexts.

In general, I think you need to have a pair of update functions for any update, one for updating classes, the other for updating objects. The real issue is when/how do you apply the update functions to objects. In any case, you will often have multiple versions of classes around at the same time. UpgradeJ (by Biermann, Parkinson and Noble) is one programming language that deals with multiple versions of a class in a type safe fashion.

The bibliography of these papers provides a few leads that you could follow. Also look on google scholar to see what paper build on these.
> 5 votes

---
Tags: reference-request, programming-languages, semantics, object-oriented
---


# Question
Title: Complexity of domino tiling with dominoes placed in a line
Let's say I have a bunch of cards or dominoes with one color on the left side of the card and another color on the right. (The two colors could be the same.) Dominoes can't be rotated so the color on each side is fixed. There is no limit on the number of colors and colors can be repeated on cards.

Dominoes are placed in a line, one after another.

The rule is, the color on the right hand side of a domino must match the color on the left hand side of the domino placed next to it.

The problem is, given a pool of dominoes, is it possible to put all of the dominoes in a line while following the rule? (I believe this is the same problem as given a group of matrices is it possible to multiply them all together.)

So for example given these dominoes: R-R, R-B, G-Y, GG-Y, Y-GG, R-R, R-B, ..., R-B, B-R, P-G is it possible to form a straight line with all adjoining sides having the same color.

My real question is this: Is the complexity of this problem (determining if it is possible to put all N dominoes in a line) NP?

# Answer
> 10 votes
This is just the Eulerian path problem on a multigraph. The colors are the vertices, and the dominos are the edges. You want to know whether there is a path that goes passes through each edge exactly once. It's polynomial time, and you should be able to find the algorithm by googling "Eulerian path".

---
Tags: complexity-theory
---


# Question
Title: Why does Prim's algorithm keep track of a node's parent?
There is an obvious similarity in workings between Prim's algorithm and Dijkstra's algorithm, however I see no reason for Prim's algorithm to keep track of a node's parent. In Dijkstra's algorithm, the parent of the node needs to be tracked in order to follow the chain back to the original node to determine the distance from the source, however since Prim's algorithm only requires knowledge of the distance from the minimal spanning tree, rather than a specific node, there would be no reason to track the parent.

Please refer to the following pseudocode as reference:

```
PRIM(V, E, w, r )
  Q ← { }
  for each u in V do
    key[u] ← ∞
    π[u] ← NIL
    INSERT(Q, u)
  DECREASE-KEY(Q, r, 0)    ▷ key[r ] ← 0
  while Q is not empty do
    u ← EXTRACT-MIN(Q)
    for each v in Adj[u] do
      if v in Q and w(u, v) < key[v] then
        π[v] ← u
        DECREASE-KEY(Q, v, w(u, v))

```

# Answer
Keeping the parent of each vertex is not a requirement to get the minimum spanning tree. For example, the algorithm as described on Wikipedia does not do this.

However, it's worth noting that there is more than one representation of an MST. In certain applications, it might be useful to quickly find the parent of a particular vertex.
> 4 votes

---
Tags: algorithms, graphs
---


title: Is Huffman Encoding always optimal?

text:
# Question
Title: Is Huffman Encoding always optimal?
The requirement of the encoding to be *prefix free* results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more efficient than encoding the data?

# Answer
> 4 votes
The entropy `H(A)` for this problem is `1.998`. Both Huffman coding and fixed length coding for this problem has avg codeword length as `2`. And FYI the coding you have got using Huffman Encoding is wrong. Huffman Encoding also produces codes similar to fixed length for this problem. It uses greedy approach. So `a` doesn't get a code as `0` but instead it gets `00`. Rework on the tree you generate using Huffman Coding. The tree you should get is:

# Answer
> 9 votes
Huffman coding approximates the population distribution with powers of two probability. If the true distribution does consist of powers of two probability (and the input symbols are completely uncorrelated), Huffman coding is optimal. If not, you can do better with range encoding. It is however optimal among all encoding that assign specific sets of bits to specific symbols in the input.

# Answer
> 8 votes
Yes, it is always optimal.

No, there is no threshold where it would use less space to use fixed length non-encoded data.

I found a number of proofs on the Web, but there is sufficient discussion in the Wikipedia article *Huffman coding*.

This also covers other techniques which achieve higher compression (working outside the space for which the Huffman code is optimal).

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


# Question
Title: Why larger input sizes imply harder instances?
*Below, assume we're working with an infinite-tape Turing machine.*

When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I stumbled across the following claim:

> \[..\] For example, it's natural that you'd need more steps to multiply two integers with 100000 bits, than, say multiplying two integers with 3 bits.

The claim is convincing, but somehow hand-waving. In all algorithms I came across, the larger the input size, the more steps you need. In more precise words, the time complexity is a monotonically increasing function of the input size.

> Is it the case that time complexity is *always* an increasing function in the input size? If so, why is it the case? Is there a *proof* for that beyond hand-waving?

# Answer
> 13 votes
> Is it the case that time complexity is always an increasing function in the input size? If so, why is it the case?

No. Consider a Turing machine that halts after $n$ steps when the input size $n$ is even, and halts after $n^2$ steps when $n$ is odd.

If you mean the complexity of a *problem*, the answer is still no. The complexity of primality testing is much smaller for even numbers than for odd numbers.

# Answer
> 4 votes
> Is it the case that time complexity is always an increasing function in the input size? If so, why is it the case? Is there a proof for that beyond hand-waving?

Let $n$ denote the input size. To read the entire input, a turing machine already needs $n$ steps. So if you assume that an algorithm has to read it's entire input (or $n/c$ for some constant $c$), you will always end up with at least linear run time.

---

The problem with defining algorithms with a "monotonically decreasing run time function" is, that you have to define the run time for $n = 1$ somehow. You have to set it to some *finite* value. But there are *infinite* possible values for $n \> 1$, so you end up with a function which is constant for infinite many values.

---

Probably *sublinear algorithms* are of interest for you, which do not read the entire input. See for example http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Sublinear-time-Survey-BEATCS.pdf.

# Answer
> 1 votes
The relation $(\mathbb{N},\leq)$ is well-founded, i.e. there are no infinite falling sequences in the natural numbers. Since (worst-case) runtime functions map to the naturals, all runtime functions therefore *have* to be in $\Omega(1)$, that is all runtime functions are (in the limit) non-decreasing.

That said, *average* runtimes can contain oscillating components, for example Mergesort.

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


# Question
Title: What are the rudimentary types of information connectivity i.e. model types?
I am looking at a modelling tool and are trying to determine all the types of ways that you can model (at a rudimentary level)

I remember seeing a list of ways in which you can connect or categorise information elements. basically the types were as follows:

* Lists - constitute a list of information elements
* Hierarchies- visualise information in a parent-child relationship (ie organisational chart)
* Flows - connect elements in a logical (lateral) flow (ie process model)

Have you seen any reference to these types, or can you elaborate on the full list of "model types"

# Answer
Model theory, branch of mathematical logic, is based on three things: atoms, functions, and relations. With these you can define pretty much anything. In fact, functions are subsumed by relations, so you only need two.

What is a list but a *next* relation? What is a hierarchy but a parent-child relation?

Of course these satisfy axioms, and these can readily be expressed in first order logic.
> 6 votes

---
Tags: data-structures, information-theory, modelling, structured-data
---


# Question
Title: How to show two models of computation are equivalent?
I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea about what it means for two models of computation to be equivalent (the automata view: if they accept the same languages). Are there other ways of thinking about equivalence? If you could help me understand how to prove that the Turing-machine model is equivalent to lambda calculus, that would be sufficient.

# Answer
> 21 votes
You show that either model can *simulate* the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is).

Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions are outlined. If you did this formally, you would take a general Turing machine (a tuple) and explicitly construct what the corresponding 2-PDA would be, and vice versa.

---

Formally, such a simulation may look like this. Let

$\qquad \displaystyle M = (Q,\Sigma\_I,\Sigma\_O,\delta,q\_0,Q\_F)$

be a Turing machine (with one tape). Then,

$\qquad \displaystyle A\_M = (Q \cup \\{q^\*\_1,q^\*\_2\\},\Sigma\_I,\Sigma\_O', \delta', q^\*\_1, Q\_F)$

with $\Sigma\_O' = \Sigma\_O \overset{.}{\cup} \\{\\$\\}$ and $\delta'$ given by

$\quad \displaystyle (q^\*\_1,a,h\_l,h\_r) \to\_{\delta'} (q^\*\_1,ah\_l,h\_r)$ for all $a \in \Sigma\_I$ and $h\_r,h\_l \in \Sigma\_O$,
$\quad \displaystyle (q^\*\_1,\varepsilon,h\_l,h\_r) \to\_{\delta'} (q^\*\_2,h\_l,h\_r)$ for all $h\_r,h\_l \in \Sigma\_O$,
$\quad \displaystyle (q^\*\_2,\varepsilon,h\_l,h\_r) \to\_{\delta'} (q^\*\_2,\varepsilon,h\_lh\_r)$ for all $h\_r,h\_l \in \Sigma\_O$ with $h\_l \neq \\$$,
$\quad \displaystyle (q^\*\_2,\varepsilon,\\$,h\_r) \to\_{\delta'} (q\_0,\\$,h\_r)$ for all $h\_r \in \Sigma\_O$,
$\quad \displaystyle (q,\varepsilon,h\_l,h\_r) \to\_{\delta'} (q',\varepsilon,h\_la) \iff (q,h\_r) \to\_\delta (q',a,L)$ for all $q \in Q$ and $h\_l \in \Sigma\_O$,
$\quad \displaystyle (q,\varepsilon,\\$,h\_r) \to\_{\delta'} (q',\\$,\square a) \iff (q,h\_r) \to\_\delta (q',a,L)$ for all $q \in Q$,
$\quad \displaystyle (q,\varepsilon,h\_l,h\_r) \to\_{\delta'} (q',ah\_l,\varepsilon) \iff (q,h\_r) \to\_\delta (q',a,R)$ for all $q \in Q, h\_l \in \Sigma\_O'$,
$\quad \displaystyle (q,\varepsilon,h\_l,\\$) \to\_{\delta'} (q,h\_l,\square\\$)$ for all $q \in Q$ and $h\_l \in \Sigma\_O'$, and
$\quad \displaystyle (q,\varepsilon,h\_l,h\_r) \to\_{\delta'} (q',h\_l,a) \iff (q,h\_r) \to\_\delta (q',a,N)$ for all $q \in Q,h\_l\in\Sigma\_O'$

is an equivalent 2-PDA. Here, we assume that the Turing machine uses $\square \in \Sigma\_O$ as blank symbol, both stacks start with a marker $\\$\notin \Sigma\_O$ (which is never removed) and $(q,a,h\_l,h\_r) \to\_{\delta'} (q',l\_1\dots l\_i,r\_1\dots r\_j)$ means that $A\_M$ consumes input $a$, switches states from $q$ to $q'$ and updates the stacks like so:

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

It remains to show that $A\_M$ enters a final state on $x \in \Sigma\_I^\*$ if and only if $M$ does so. This is quite clear by construction; formally, you have to translate accepting runs on $M$ into accepting runs on $A\_M$ and vice versa.

# Answer
> 4 votes
At the beginning of **Communicating and Mobile Systems: the Pi-Calculus** by Robin Milner, there is a introduction on automata and how they can simulate each other so that they cannot be distinguished : **Bisimulation**. (cf Bisimulation on wikipedia)

I don't remember well, I should re-read the chapter, but there was a trouble with simulation and bisimulation that made them not sufficient for computational equivalences.

Thus Robin Milner introduces his Pi-Calculus and exposes it for the rest of the book.

Ultimately, in his last book **The Space and Motion of Communicating Agents**, you could have a look at Robin Milner's Bigraphs. They can model Automata, Petri nets, Pi-Calculus and other computational methodologies.

# Answer
> 2 votes
As far as I know, the only (or at least most common) way to do this is to compare the languages the machines/models accept. That's the whole point of Automata theory: it takes the vague concept of a problem or algorithm and turns it into a concrete mathematical set (i.e. a language) which we can reason about.

The easiest way to do this is, given an arbitrary machine/function from one model, to construct a machine from the second model that computes the same language. Odds are you'll use induction in the length of the expression, states in the machine, rules in the grammar, etc.

I haven't seen this done with Lambda and TMs (though I'm 99% sure it's possible), but I have definitely seen this kind of thing for proving equivalence of NFAs and Regular expressions. First you show a NFA which can accept any atom, then using induction, you make NFAs which accept the union/concatenation/Kleene-star of any smaller NFAs.

Then you do the opposite, to find an RE for any NFA.

---
Tags: proof-techniques, computation-models, simulation
---


title: Floating point rounding

text:
# Question
Title: Floating point rounding
Can an IEEE-754 floating point number \< 1 (i.e. generated with a random number generator which generates a number \>= 0.0 and \< 1.0) ever be multiplied by some integer (in floating point form) to get a number equal to or larger than that integer due to rounding?

i.e.

```
double r = random() ; // generates a floating point number in [0, 1)
double n = some_int ;
if (n * r >= n) {
    print 'Rounding Happened' ;
}

```

This might be equivalent to saying that does there exist an N and R such that if R is the largest number less than 1 which can be represented in IEEE-754 then N * R \>= N (where * and \>= are appropriate IEEE-754 operators)

This comes from this question based on this documentation and the postgresql random function

# Answer
Assuming round-to-nearest and that $N \> 0$, then $N * R \< N$ always. (Be careful not to convert an integer that's too large.)

Let $c 2^{-q} = N$, where $c \in \[1, 2)$ is the significand and $q$ is the integer exponent. Let $1 - 2^{-s} = R$ and derive the bound

$$N R = c 2^{-q}(1 - 2^{-s}) \le c 2^{-q} - 2^{-q - s},$$

with equality if and only if $c = 1$. The right-hand side is less than $N$ and, since $2^{-q - s}$ is exactly $0.5$ units in the last place of $N$, either $c = 1$ and $2^{-q} - 2^{-q - s}$ is exactly representable (since $N$ is normal and not the smallest normal), or $c \> 1$, and the nearest rounding is down. In both cases, $N * R$ is less than $N$.

---

Upward rounding can cause a problem, not that it should ever be selected in the presence of unsuspecting users. Here's some C99 that prints `"0\n1\n"` on my machine.

```
#include <fenv.h>
#include <math.h>
#include <stdio.h>

int main(void) {
    double n = 10;
    double r = nextafter(1, 0);
    printf("%d\n", n == (n * r));
    fesetround(FE_UPWARD);
    printf("%d\n", n == (n * r));
}

```
> 9 votes

---
Tags: numerical-analysis, floating-point, rounding
---


# Question
Title: Decider for the family of Turing machines that move infinitly to the right on some input
I need help finding an algorithm which, given a Turing machine description $\langle M \rangle$, decides whether there exists an input $w$ such that in the computation of $M(w)$, the head only moves right and $M$ never stops.

# Answer
Given a Turing machine $M$ for which such an input exists, what does $M$'s state graph look like?

> For some input $w$, there is a computation of the form $q\_0 \leadsto q (\leadsto q)^\omega$ whose transitions all have movement $R$ (or $N$, depending on the meaning of "only"). Therefore, the state graph has to have an "$R$-path" from $q\_0$ to some $q$ which lies on an "$R$-cycle".

Is this also a sufficient criterion? The answers to both questions lead you towards a decision procedure.
> 7 votes

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


# Question
Title: Pumping Lemma: is it valid to "multiply the product of powers" in this case?
I need to show that

$\qquad \displaystyle S = \\{(10^p)^m \mid p \geq 0, m \geq 0\\}$

is not a regular language using pumping lemma.

Can I multiply the product of the powers and express it to: $S = \\{ 1^m 0^{pm} \mid \dots \\}$ and apply the pumping lemma where I pump 1's then say that the language doesn't accept the new string?

# Answer
You're right, the superscript in this context means concatenation.

To prove a language isn't regular, you use the fact that any regular language can be "pumped". First, find out what "pumping" a word means (I can't do your homework for you), and then show that your language can not be pumped, and thus, can not be regular. Basically you will take a sufficiently long word that belongs to your language, and show that it cannot be broken up and pumped in such a way that it satisfies the pumping lemma.

Note that the converse of the pumping lemma is not always true: that is, if a language does NOT satisfy the pumping lemma, it may still be non-regular. For this reason, the pumping lemma is used to exclude a language from a set of languages, and not to include a language in a set of languages (such as regular). In other words, satisfying the pumping lemma is a necessary, but not sufficient, condition for a language to be regular.
> 7 votes

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


title: Is this language Context-Free?

text:
# Question
Title: Is this language Context-Free?
> **Possible Duplicate:**
> Is this language Context-Free?

The language is defined by $$(a+b)^\*-\\{(a^nb^n)^n\mid n \geq1 \\}$$

is Context-Free Language? I believe that the answer is that it is not a CFL's, but I can't prove it by Ogden lemma or pumping lemma.

chazisop, (a+b)\* means {a,b}\*. That's all strings that you can form with the symbols a or b or both.

# Answer
If I understand the notation correctly, only $ab$ can fit both $(a+b)^{\*}$ and $(a^{n}b^{n})^{n}$. I see no other way of stacking more $b$'s after the a's, since $a+$ suggest you should have at least one $a$ in every repetition of the expression in parentheses.

$(a+b)^{\*}-ab$ seems like a regular language to me, since $ab$ rejects, $a+b$ just consumes one or more $a$'s before a $b$. If we can construct a DFA for $a+b$, we can construct one for $(a+b)^{\*}$ as well.
> -2 votes

---
Tags: formal-languages, automata
---


# Question
Title: The essential difference between spiking neural networks and earlier generation ANN's
I have been studying Spiking Neural Networks online from various papers, mainly Maass (1997). I am not entirely sure I understand what makes SNN's pulse-code in contrast to earlier ANNs which are considered rate-code. I have background in neuroscience so I understand the terms and ratio, I'm asking regarding the actual implementation.

Is the practical difference in the fact that when each neuron updates its current state in an SNN it deals with the entire history of every pre-synaptic neuron and not only the last step? Is that what gives it temporal characteristics which previous generation ANN's lack?

# Answer
> 1 votes
Yeah; each neuron in the spiking network integrates its input, instead of just summing the input of the previous timestep as in the old analog model.

---
Tags: terminology, artificial-intelligence, neural-networks
---


# Question
Title: Batch processing in increase-key function using binary heap
Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one node, then we have to traverse paths from the node towards the children to re balance the heap. If we want to increase the keys of five nodes in the heap, we need to call the increase-key function five times. Is it possible to call only one increase-key function and perform increase-key on five nodes simultaneously?

# Answer
If $P$ is the number of processing units available, consider $P$-ary heaps¹. When descending to perform some operation on a *set* of keys, you can fork whenever keys lead to different children. If the heap is balanced, this results in independent taks for a uniformly chosen set of keys (and sufficiently big $n$) after having descended a constant number of levels (claim).

The above can only be expected to work well on shared memory systems. As soon as you have NUMA or distributed memory, you want to assign one subtree to every processing unit (and its memory). I suggest you give the root $P$ children, each of which is an (arbitrary) heap in its own right. All operations are send as messages to the corresponding subtree's processing unit. Operations that need the subtrees to interact block the root.

---

1. I *think* $P$ would be the correct branching degree, but you'd have to do some analysis and/or experiments.
> 5 votes

---
Tags: algorithms, data-structures, parallel-computing, concurrency, priority-queues
---


title: Undergraduate studies: Math or CS?

text:
# Question
Title: Undergraduate studies: Math or CS?
hope it's possible for this question to be answered in an objective manner.

I'm not studying in a liberal arts college so basically I only get to study one subject. Which would be the better preparation for future research (probably grad school) into theoretical CS? The standard undergraduate math course with analysis and algebra, or the standard undergraduate CS course with algos and concurrency and the like.

# Answer
Echoing Raphael's comments, this is highly subjective without knowing you personally. However, here are the things I'd consider:

Many schools are flexible for your undergrad program, meaning that what you choose likely won't affect your graduate career too too much, particularly if you take a good number of classes in each subject.

Do you like calculus/real analysis, or only discrete math? It varies from school to school, but if you're not into calculus at all, probably better to stick with CS.

Likewise, do you want to learn programming? If you have no interest in learning about caching, hardware, programming language concepts, or more "applied" aspects of computer science, then Math might suit you better. Many undergraduate CS programs serve the dual purpose of preparing coders for industry and preparing future grad students. You will likely have to take non-theoretical classes at some point.

Are you more interested in creating new algorithms, or analysing discrete structures? My guess is that CS will beter prepare you for creating new algorithms and solving problems, while Math will better prepare you for detailed proofs about discrete structure.

I would reccomend at least taking a few comp-sci classes. My experience is that people with a math backgorund, but not a computer science background, aren't equipped as well to communicate about things like algorithms and pseudocode. As an example, when talking about Breadth First Search in a math Graph Theory class, the professor had to go and define what a queue was. In a CS class, data structures will be something you cover once and then can keep using later on. Likewise, the pseudocode I've encountered in such classes was full of numbered steps and GOTOs, as apposed to the clean iterative or recursive definitions from CS classes.
> 5 votes

---
Tags: education
---


# Question
Title: Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?
After looking at other questions and my textbook, I seem to get some confusion.

I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem.

But the statement describing reduction seems obscure to me at least in the beginning of my studies in computational complexity.

So, can we transform an exponential algorithm for NPC (which we have) into an exponential algorithm for another non-NPC NP problem in polynomial time?

# Answer
If you have an algorithm running in time $f(n)$ that solves an $\mathsf{NP\text{-}complete}$ problem, you can use it to solve any $\mathsf{NP}$ problem and the running time will be $g(n)=f(n^k) + p(n)$ ($k$ is a constant which depends on the reduction between the problems, $p(n)$ is a polynomial essentially giving the running time of the reduction function).

I am not sure what you mean exactly by exponential time, but the result above is general and will work for any $f$, e.g.:

1. If $f$ is a polynomial, then $g(n)$ is also a polynomial,
2. If $f(n) = 2^{\epsilon n}$, then $g(n) = 2^{\epsilon n^k}+p(n)$,
3. If $f(n)= 2^{n^\epsilon}$ then $g(n) = 2^{n^{k\epsilon}}+p(n)$.

---

I am not sure what you exactly mean by transforming an algorithm, but

**what is essentially needed is that we are given a reduction algorithm from $Q'$ to $Q$. If we have that, it is easy to compose it with any algorithm $A$ for $Q$ to obtain an algorithm for $Q'$.** If this is given as an input to the transformation, it can transform an algorithm $A$ for $Q$ to an algorithm for $Q'$ very easily (in polynomial time): it will output the code resulting from composing the code for the reduction from $Q'$ to $Q$ with the code for the algorithm $A$. In fact, this can be done in linear time.

If the reduction is not given as an input then the algorithm has to find it. It can be done under some conditions but essentially we have to provide the transformation with enough information so that the transformation can find the needed reduction algorithm. If we don't provide enough information to find the reduction then this cannot be done. At least not uniformly in $A$. Here is an argument:

The transformation has to return an algorithm that is essentially the composition of a reduction function from $Q'$ to $Q$ with $A$. However the transformation cannot check what a given algorithm $A$ for $Q$ is really doing (because of Rice's theorem). So we can give an identity algorithm as $A$ and the transformation will not notice this and will return an algorithm which is essentially the composition of a reduction from $Q'$ to $Q$ with the identity function. But that is equal to the reduction function from $Q'$ to $Q$. So the output will be a reduction algorithm from $Q'$ to $Q$.
> 4 votes

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


title: Universal simulation of Turing machines

text:
# Question
Title: Universal simulation of Turing machines
Let $f$ be a fixed time-constructable function.

The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given

* the description of a TM $\langle M \rangle$, and
* an input string $x$,

runs for $g(|x|)$ steps and returns $M$'s answer on $x$. And $g$ can be taken to be any function in $\omega(f(n)\lg f(n))$.

My questions are:

> 1. What is the best known simulation result on a single tape TM? Does the result above also still hold?
> 2. Is there any improvement on \[HS66\]? Can we simulate TMs on a two-tape TM for $f(n)$ steps in a faster way? Can we take $g(n)$ to be in $\omega(f(n))$ in place of $\omega(f(n)\lg f(n))$?

# Answer
> What is the best known simulation result on a single tape TM? Does the result above also still hold?

We can simulate a multiple-tape TM on a single-tape TM with quadratic increase in time. The simulation time is $O(n^2)$. The quadratic increase is required since there are languages (e.g. palindromes) that require time $\Omega(n^2)$ on a single-tape DTM but can be solved in time $O(n)$ on a two-tape DTM.

In short, the result above does not work when the simulator is a single-tape TM.

For simulation of *single-tape TMs* on a single-tape TM (with arbitrary finite alphabet), the result holds, i.e. the simulation can be done with $\lg$ factor increase in time. See (2) and (3). The reference seems to be (6).

> Is there any improvement on \[HS66\]? Can we simulate TMs on a two-tape TM for $f(n)$ steps in a faster way? Can we take $g(n)$ to be in $\omega(f(n))$ in place of $\omega(f(n)\lg f(n))$?

It seems that there hasn't been any improvement since that would imply a better time hierarchy theorem than currently known.

Correction: The usual hierarchy theorems are based on time complexity classes defined using single tape TMs. For $n$-tape TMs a tight result similar to the space hierarchy theorem is proven by Furer in 1982 (5). The $\lg$ factor is not needed. Also see (4).

References:

1. Peter van Emde Boas, "Machine Models and Simulation", in Handbook of Theoretical Computer Science, 1990
(in particular, pp. 18-21)
2. Michael Sipser, "Introduction to the Theory of Computation", 2006
(time complexity classes are defined using TMs with single-tape infinite in both directions and arbitrary finite alphabet, see pages 140 and 341)
3. Odifreddi , "Classical Recursion Theory", vol. I & II, 1989 & 1999
(definitions are similar to Sipser, see Def. I.4.1 in vol. I page 48, Def. VII.4.1 in vol. II page 67, and Thm. VII.4.15 in vol. II page 83)
4. Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999
(page 84)
5. Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982
6. Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968
7. F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966
8. Other related questions:

1. Lower bounds and class separation,
    2. Justification of $\lg f$ in DTIME hierarchy theorem,
    3. Alphabet of single-tape Turing machine,
    4. For the time hierarchy theorem, how is the input translated efficiently?,
    5. a comment by Luca Trevisan.
> 7 votes

---
Tags: complexity-theory, reference-request, turing-machines, machine-models, simulation
---


title: Good text on algorithm complexity

text:
# Question
Title: Good text on algorithm complexity
Where should I look for a good introductory text in algorithm complexity? So far, I have had an Algorithms class, and several language classes, but nothing with a theoretical backbone. I get the whole complexity, but sometimes it's hard for me to differentiate between O(1) and O(n) plus there's the whole theta notation and all that, basic explanation of P=NP and simple algorithms, tractability. I want a text that covers all that, and that doesn't require a heavy mathematical background, or something that can be read through.

LE: I'm still in highschool, not in University, and by heavy mathematical background I mean something perhaps not very high above Calculus and Linear Algebra (it's not that I can't understand it, it's the fact that for example learning Taylor series without having done Calculus I is a bit of a stretch; that's what I meant by not mathematically heavy. Something in which the math, with a normal amount of effort can be understood). And, do pardon if I'm wrong, but theoretically speaking, a class at which they teach algorithm design methods and actual algorithms should be called an "Algorithms" class, don't you think? In terms of my current understanding, infinite series, limits and integrals I know (most of the complexity books I've glanced at seemed to use those concepts), but you've lost me at the Fast Fourier Transform.

# Answer
It is my very personal opinion that the book of Jon Kleinberg and Éva Tardos is the best book for studying the design and analysis of efficient algorithms. It might be not as comprehensive as *Cormen et al.* but it is a great textbook. Let me point out, why I think this book might suit your interests best

* you don't need heavy math machinery for the proofs
* the book gives often a great intuition why something is working (or not), this is in my opinion very important for beginners and self learners
* a very intuitive approach to NP-completeness
* it has a great chapter how to deal with NP-complete problems in practice
* it focuses on design patterns, which might help you to design your own clever algorithms

You should also notice, that there is a lot of free material in the WWW available. Great lecture notes are provided by Jeff Erickson. And you can even watch the whole MIT class on "Introductions to algorithms" taught by Charles Leiserson and Erik D. Demaine. Cool stuff!
> 5 votes

# Answer
You can surely bet for the famous book of *Cormen et al.* "Introduction To Algorithms". First of all it's quite difficult to understand the book if you don't have sound mathematical base. But for the shake of easy understanding you can skip those mathematical proofs (not recommended). Also you can go for Algorithm Design Manual.
> 3 votes

# Answer
You should have a look at M. Sipser's "Introduction to the Theory of Computation". I did read (and understood) this book when I was in High School, so I think it is suitable for you.

Although it's quite formal, everything is also explained in plain English. It also has a little introduction to proof techniques at the beginning.

---

Note: If you want to do CS on a serious level (e.g. research) you need a *solid* background in math. There is no short cut. Have a look at i.e. Graham, Knuth and Patashnik's Concrete Mathematics.
> 3 votes

---
Tags: complexity-theory, reference-request, algorithm-analysis, education, books
---


# Question
Title: Is every linear-time algorithm a streaming algorithm?
Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear time algorithms. This is a bit bold as in general, a linear time algorithm can jump around at will (random access) which a streaming algorithm can not; it has to investigate the elements in order. I may perform multiple passes, but only constantly many (for linear runtime).

Therefore my question:

> Can every linear-time algorithm be expressed as a streaming algorithm with constantly many passes?

Random access seems to prevent a (simple) construction proving a positive answer, but I have not been able to come up with a counter example either.

Depending on the machine model, random access may not even be an issue, runtime-wise. I would be interested in answers for these models:

* Turing machine, flat input
* RAM, input as array
* RAM, input as linked list

# Answer
For streaming algorithms to be meaningful, they have to work with significantly smaller amount of work space than the input itself. For example, if you allow the same amount of work space as the input, then you can trivially state any algorithm as a “single-pass streaming algorithm” which first copies the input to the work space in single pass and then only use the work space.

I think that it is typical to restrict the work space to at most polylogarithmic in the input size when talking about streaming algorithms. Under this assumption, median selection does not have an O(1)-pass streaming algorithm by the result of Munro and Paterson \[MP80\]: any *P*-pass streaming algorithm for median selection on *N* elements has to store Ω(*N*1/*P*) elements. On the other hand, median selection has a well-known deterministic linear-time algorithm \[BFPRT73\].

\[BFPRT73\] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. *Journal of Computer and System Sciences*, 7(4):448–461, Aug. 1973. DOI: 10.1016/S0022-0000(73)80033-9

\[MP80\] J. Ian Munro and Mike S. Paterson. Selection and sorting with limited storage. *Theoretical Computer Science*, 12(3):315–323, Nov. 1980. DOI: 10.1016/0304-3975(80)90061-4
> 15 votes

# Answer
In the streaming model you are only allowed to store constant or poly-logarithmic extra-data while scanning through the input. If you consider a linear time algorithm
that follows the *divide and conquer* paradigm, you need to store more information and/or you should scan through your data as many times as the depth of the recursion.

One example is the DC3 algorithm for constructing the suffix array of a text $T$ (given as array in the RAM model). In order to construct a suffix array, you group the characters into triplets, so you get a text with new *super-characters*. You can do this with an offset of $0,1,2$, which results in three new texts $T\_1,T\_2,T\_3$. Interestingly, you can compute the suffix array if you have the suffix array of $T\_1\cdot T\_2$ in linear time. Hence the algorithm needs

$$ t(n)= t(2/3 \\;n) + O(n) $$

time. This recursion solves clearly to $t(n)=O(n)$. I don't see how this can be turned into a streaming algorithm.

Another well known example is the classical linear-time selection algorithm.
> 6 votes

# Answer
I interpret your question as follows. Let's fix some computational problem $P$. We define:

* $R(P)$ is the smallest workspace that any linear time random access algorithm for $P$ can have. I think the exact model does not matter all that much, but let's say that the we have a word RAM which is given the input as a random-access read-only array.
* $S(P)$ is the smallest workspace that a sequential algorithm for $P$ can have; here we assume that the algorithm (which is again modeled as a word RAM machine) proceeds in time steps: at each time step one cell of the input array is given, the algorithm does some processing, records some information in its local storage, and then proceeds to the next time step. The array is "looped over" a constant number of times in this manner.

So I think you are asking about how big the gap between $R(P)$ and $S(P)$ can be.

On the low end of the spectrum, there is an answer in Muthu's streaming book. Look at puzzle 3. The problem is, given an array of $n$ integers, all in the range $\[1, n-1\]$, find a duplicated integer. There exists a random access linear time solution with $O(\log n)$ bits (equivalently, $O(1)$ number of words): basically pointer-chasing. But a constant pass algorithm must necessarily have $\omega(\log n)$ space complexity.

There is an aspect of the model that we have not quite fixed: what direction do the passes go? I.e., once we feed the streaming algorithm the entire array, does the next pass start from the end or the beginning? Interestingly, this can make a big difference. Consider the problem of recognizing a well-parenthesizes expression where there are two types of parentheses. Say we want the probability of error to be $O(1/\log^2 n)$. Then Chakrabarti et al. show that if we restrict all passes to go in one direction, we have $ps = \Omega(\sqrt{n})$, where $p$ is the number of passes and $s$ is the space complexity. On the other hand, Magniez et al. give a simple algorithm that uses $O(\log^2 n)$ space, has polynomially small probability of a false positive, and makes one pass forward and one backwards.
> 4 votes

# Answer
Even in the simplest definition of "streaming algorithm" (an algorithm which, after every incremental iteration on the source, results in the immediate knowledge of the next incremental piece of the result), I can think of a few linear algorithms that don't behave that way. Hashing algorithms are a big one; FNV-1a is linear to the number of bytes in the source, but we don't know any part of the final hash until the full source has been processed.

RadixSort aka BucketSort is O(N) (technically O(NlogM) where M is the maximum value in the N items, which is considered small), and must run in its entirety to guarantee that any individual item is in its final place.

To be a "streaming" algorithm, at its simplest, an algorithm must have the following two properties, neither of which are expressly time-bound:

* **Better than O(N) space complexity** (stated equivalently, the entire source doesn't have to be known and the entire result doesn't have to be stored)
* **O(N) I/O relationship** (the algorithm produces a number of outputs linearly proportional to its inputs)

Therefore, the main class of algorithms that stream is that of algorithms that perform "projections" (incremental transformations of one input to X\>0 outputs).
> 1 votes

---
Tags: algorithms, streaming-algorithm, simulation, lower-bounds
---


# Question
Title: How are all NP Complete problems similar?
I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

1. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified in polynomial time.
2. Take any known NP-complete problem (call "Easy") and reduce **all** of it's instances to **few** instances of given problem (call "Hard"). Note this is **not** necessarily an 1:1 mapping.
3. Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP-complete problem in polynomial time, then all NP-complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?

# Answer
Your question seems to come from the fact that you're not immediately convinced that the current problem can't be harder. The current problem can't be harder than any NP-complete problem because it is in NP.

If you want to be convinced that the notion of NP-completeness even exists (i.e. that you can reduce anything in NP to an NP-complete problem) you should study the Cook-Levin theorem which states that SAT is NP-complete.

Since NP-completeness states something about being the target of a reduction from *any* problem in NP, the proof works by encoding the Turing machine which was the verifier of the original problem as a formula. This formula is satisfiable if and only if there exists an input which lets the Turing machine accept. You could in principle use this proof to reduce your current problem to SAT, and after that to every other NP-complete problem via transitivity of polynomial-time reductions.
> 13 votes

# Answer
You are confused by the direction of the reduction. So let me explain how to argue.

You have a language, say $L$ and you want to show that it is NP-complete. First you show that is indeed in NP, i.e., by finding a good certificate. Thus you are left by showing the NP-hardness. This can be done by reducing some NP-complete language $L\_\text{NPC}$ **to** your language $L$, by a polytime many-one reduction. This means you define a polytime function, that maps yes-instances of $L\_\text{NPC}$ to yes-instances of $L$, and that maps no-instances of $L\_\text{NPC}$ to no-instances of $L$.

By the transitivity of polytime many-one reductions, every language in NP can now be reduced to $L$ (take a detour over $L\_\text{NPC}$). On the other hand, if there exist a deterministic polynomial time algorithm $A$ that decides $L$, we can decide every language in NP in polynomial time, by first reducing it to $L$ and then asking $A$.

It seems that you have just thought in the wrong direction. The problem that you called "easy", can be solved with help of the reduction and the problem you call "hard". First of all, this is strange misleading terminology, and second, it should probably be the other way around.
> 10 votes

# Answer
Given a set $A \subset \mathbb R$, how do you show that $a$ is a greatest element of the set $A$? There are two steps:

1. Show that $a \in A$.
2. Show that for any $b \in A$, $b \leq a$.

If $a,b$ are greatest elements of set $A$, then applying condition 2 twice (for $a$ and $b$) you get $a \leq b \leq a$. In $\mathbb R$ this means $a=b$ and a set can only have a single greatest element.

---

Now replace $\mathbb R$ by $A^{\ast}$ and $\leq$ by existence of polynomial time reduction. To show that $L$ is NP-complete, there are to steps:

1. Show that $L \in \mathsf{NP}$.
2. Show that for any $L' \in \mathsf{NP}$, $L' \leq L$. This condition is called NP-hardness.

If $L,M$ are two NP-complete languages, then applying condition 2 twice you get $L \leq M \leq L$. Which means the problems are equivalent: if you are able to solve $L$, then you can solve $M$ and vice-versa. Unlike in reals, it might be true that $L \neq M$. Let $L \sim M$ mean $L \leq M \leq L$. You can show this is an equivalence relation.

---

Exercise.

Assume that $M$ is NP-complete, and that $L \sim M$. Show that $L$ is NP-complete.

1. Show that $L \in \mathsf{NP}$.

> Since $M$ is in NP, and $L \leq M$, a machine recognizing $L$ can just use the reduction.
2. Show that for any $L' \in \mathsf{NP}$, $L' \leq L$.

> Since $M$ is NP-hard, $L' \leq M$. Since we know $M \leq L$, by transitivity $L' \leq L$.

---

Therefore, if two languages are NP-complete, they are equivalent. If a language is equivalent to NP-complete language, it is also NP-complete.
> 4 votes

# Answer
There seem to be two misconceptions here.

1. "Easy" and "hard": if anything, it's the other way round. The given problem is "easy" (we don't know its complexity), the other one is *known* to be hard.
2. "reduce **all** of it's instances to **few** instances of given problem": the emphasis is misleading. It's not important how large the reduction's value range is. What is central is that the reduction preserves whether the instance is a YES-instance. In other words, the instance of the NPC problem is a YES instance if and only if its reduction image is a YES instance for the given problem.

Then, what you do is to show that you can solve the hard problem by mapping its instances to instances of the given one (in polynomial time) and solve those. Therefore, the hard problem can not be harder than the given one. Equivalently, the given problem is at least as hard as the hard problem. Quod erat demonstrandum.
> 1 votes

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


# Question
Title: Asymptotic growth rate of $f(n)$ and $f(n+1)$
Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds:

$\qquad f(n+1) = \Theta(f(n))$

# Answer
> 6 votes
Imagine any continuous, monotonically non-decreasing function $f$ such that $f(n) = n!$ for all non-negative integers $n$. Then $f(n+1) = (n+1)! = (n+1)n! = (n+1)f(n)$. Since there is no constant $c$ such that $n+1\<c$, it follows that it is not true that $f(n+1) = \Theta(f(n))$. QED.

# Answer
> 3 votes
### Hint:

First consider a function $f:\mathbb{Z} \to \mathbb{Z}$ like

$$f(n) = \begin{cases} g(k) & \text{if } n=2k\in \mathbb{Z} \\ h(k) & \text{if } n=2k+1\in \mathbb{Z} \\ \end{cases}$$

Then extend it in a continuous way to a function over $\mathbb{R}$.

# Answer
> 2 votes
I read your question like this. Given such a function $f$, define $g(n) = f(n)$ and $g'(n) = f(n+1)$. Is $g' \in \Theta(g)$?

Hint 1: If this is true, for all such functions $f$ you have a $c$ such that $f(n+1) \leq c f(n)$ for all sufficiently large $n$ (by definition).

Hint 2: $f(n+1) \leq c f(n) \iff f(n+1) - f(n) \leq (c-1)f(n)$ -- does that trigger some high school maths knowledge?

Ultimate hint:

> For $f\_1(n) = n$, $f\_1(n+1)-f\_1(n) = 1$.
> For $f\_2(n) = 2^n$, $f\_2(n+1) - f\_2(n) = f\_2(n)$.
> For $f\_3(n) = ?$, ...

---
Tags: asymptotics, mathematical-analysis, landau-notation
---


title: Is $O$ contained in $\Theta$?

text:
# Question
Title: Is $O$ contained in $\Theta$?
So I have this question to prove a statement:

$O(n)\subset\Theta(n)$...

I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\subset O(n)$.

My understanding is that $O(n)$ is the set of all functions who do no worse than $n$ while $\Theta(n)$ is the set of all functions that do no better and no worse than n.

Using this, I can think of the example of a constant function say $g(n)=c$. This function will surely be an element of $O(n)$ as it will do no worse than $n$ as $n$ approaches a sufficiently large number.

However, the same function $g$ would not be an element of $\Theta(n)$ as g does do better than $n$ for large $n$... Then since $g \in O(n)$ and $g \not\in \Theta(n)$, then $O(n)\not\in\Theta(n)$

So is the question perhaps wrong ? I've learnt it is dangerous to make that assumption and usually I have missed something, I just can't see what it might be in this case.

Any thoughts ? Thanks a lot..

# Answer
> 11 votes
At the suggestion of Raphael, I have turned a previous comment into this answer.

It is not true that $O(f(n)) \subset \Theta(f(n))$. In fact, $\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$, by definition. So we have $\Theta(f(n)) \subset O(f(n))$.

# Answer
> 4 votes
Think about it this way: every function that does "no worse than n" and "no better than n" is also a function that does "no worse than n". The "no better than n" part is just an additional constraint. This is a straightforward application of the logical rule that says: $x \wedge y \implies x$. By this reasoning, all functions that are in the set $\Theta(n)$ are also members of the set $O(n)$.

---
Tags: asymptotics, mathematical-analysis, landau-notation
---


# Question
Title: Is rejection sampling the only way to get a truly uniform distribution of random numbers?
Suppose that we have a random generator that outputs numbers in the range $\[0..R-1\]$ with uniform distribution and we need to generate random numbers in the range $\[0..N-1\]$ with uniform distribution.

Suppose that $N \< R$ and $N$ does not evenly divide $R$; in order to get a **truly uniform distribution** we can use the rejection sampling method:

* if $k$ is the greatest integer such that $k N \< R$
* pick a random number $r$ in $\[0..R-1\]$
* if $r \< k N$ then output $r \mod N$, otherwise keep trying with other random numbers r', r", ... until the condition is met

> Is rejection sampling the only way to get a truly uniform discrete distribution?

If the answer is yes, why?

Note: if $N \> R$ the idea is the same: generate a random number $r'$ in $\[0..R^m-1\], R^m \>= N$, for example $r' = R(...R(R r\_1 + r\_2)...)+r\_m$ where $r\_i$ is a random number in the range $\[0..R-1\]$

# Answer
Yes and no, depending on what you mean by “the only way”. Yes, in that there is no method that is guaranteed to terminate, the best you can do (for generic values of $N$ and $R$) is an algorithm that terminates with probability 1. No, in that you can make the “waste” as small as you like.

### Why guaranteed termination is impossible in general

Suppose that you have a deterministic computation engine (a Turing machine or whatever floats your boat), plus an oracle that generates random elements of the $R$-element set $\[0..R-1\]$. Your goal is to generate an element of the $N$-element set $\[0,N-1\]$. The output of your engine depends only on the sequence of values returned by the oracle; it is a function $f$ of that potentially infinite sequence $(r\_0, r\_1, r\_2, \ldots)$.

Suppose that your engine calls the oracle at most $m$ times. There might be traces for which the oracle is called less than $m$ times; if so, calling the oracle extra times so that it is always called exactly $m$ times does not change the output. So without loss of generality, we assume that the oracle is called exactly $m$ times. Then the probability of the outcome $x$ is the number of sequences $(r\_0, \ldots, r\_{m-1})$ such that $f(r\_0, \ldots, r\_{m-1}) = x$. Since the oracle is a uniform random generator, each sequence is equiprobable and has the probability $1/R^m$. Hence the probability of each outcome is of the form $A/R^m$ where $A$ is an integer between $0$ and $R^m$.

If $N$ divides $R^m$ for some $m$, then you can generate a uniform distribution over $N$ elements by calling the random generator $m$ times (this is left as an exercise to the reader). Otherwise, this is impossible: there is no way to obtain an outcome with probability $1/N$. Note that the condition is equivalent to saying that all of $N$'s prime factors are also factors of $R$ (this is more permissive than what you wrote in your question; for example you can pick a random element among 4 with a 6-sided fair die, even though 4 does not divide 6).

### Reducing the waste

In your strategy, when $r \ge k\\,N$, you don't have to re-draw immediately. Intuitively, there's a bit of entropy left in $\[k\\,N .. R-1\]$ which you can keep in the mix.

Assume for a moment that you will in fact keep generating random numbers below $N$ forever, and you generate $u$ of them at a time by making $d$ draws. If you do a straightforward rejection sampling on this grouped generation, the waste over $d$ draws is $\dfrac{R^d - k\\,N^u}{d}$, i.e. the remainder $R^d \mathbin{\mathrm{mod}} N^u$ divided by the number of draws. This can be as little as $\gcd(R,N)$. When $R$ and $N$ are coprime, you can make the waste arbitrarily small by picking sufficiently large values of $d$. For general values of $R$ and $N$, the calculation is more complicated because you need to take into account the generation of $\gcd(R,N)$ and $N/\gcd(R,N)$ separately, but again you can make the waste arbitrarily small with large enough groups.

In practice, even with relatively inefficient random numbers (e.g. in cryptography), it is rarely worth doing anything but simple rejection sampling, unless $N$ is small. For example, in cryptography, where $R$ is typically a power of 2 and $N$ is typically hundreds or thousands of bits, uniform random number generation usually proceeds by straight rejection sampling in the desired range.
> 15 votes

# Answer
Actually, no, rejection sampling is far from the only way of proceeding. Unfortunately, considering that computers store all information as bits, and thus can only manipulate random bits of information, any algorithm to draw a uniform random variable of range $N$ will be infinite, if the binary base development of $N$ is infinite.

This theorem is a classical result by Knuth and Yao (1976), who developed the framework of DDG-trees (discrete distribution generating trees).

The methods exposed by Gilles are the typical sort of thing that has been done to mitigate the waste incurred by rejection, but of course if one can generate following Knuth and Yao's trees it is much, much more efficient - on average 96% of random bits are saved.

I have given more information on this in the following CStheory post.
> 7 votes

# Answer
Shannon's source coding theorem shows that, in some exact sense, you need $\log N/\log R$ samples (on average) of the type $\[0,\ldots,R-1\]$ to generate a random number of the type $\[0,\ldots,N-1\]$. More accurately, Shannon gives an (inefficient) algorithm that given $m$ samples of the first type, outputs $m(\log N/\log R - \epsilon)$ samples of the second type, with high probability. He also shows that outputting $m(\log N/\log R + \epsilon)$ samples with high probability is impossible.

Shannon's theorem also works in the more general case of a skewed input distribution (and probably also skewed output distribution). In that case, you need to replace the logarithm with the entropy. While the algorithm given by the theorem is defined randomly, in some cases it is possible to derandomize it (at the cost of somewhat worse performance).
> 6 votes

---
Tags: probability-theory, randomness, random-number-generator, sampling
---


# Question
Title: Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT
In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof involves some clever construction which reduces all instances of $K$ to few instances of $L$. Here is the proof order they follow. **CIRCUIT-SAT, SAT, 3 CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP**. e.g. in reducing **VERTEX-COVER** to **HAM-CYCLE** they use a **widget** which does the trick.

After this previous question of mine, I think one can reduce back. i.e. one can reduce **HAM-CYCLE** to **VERTEX-COVER** problem. I tried searching web for such reductions, but most of the link return the normal reduction order. I'm interested to see if one can reduce in **reverse order**. i.e. TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

I'm looking for reverse constructive proofs. I know all of these problems belong to NP-complete hence equivalent.

You don't have to give complete proof as an answer. Proof sketches are fine too. If you can point me where these proofs are available online, that's completely fine too. I'm just trying to lean how constructions are leveraged among problems that look so different on surface. Thanks!

# Answer
A couple of the ones you're looking at here are pretty simple actually (at least to sketch!). For all of these, there are many other ways to do it, even many other sensible ways, so these are just attempts to pick the simpler approaches (we'll see if I succeed).

As mentioned in one of the comments on the question, $3SAT$ to $SAT$ is trivial, an instance of $3SAT$ is already and instance of $SAT$, so there's no work needed at all.

To get from $VERTEX$ $COVER$ $(VC)$ to $CLIQUE$ we can do a couple of short jumps, that'll also put another problem in the loop. $VC$ is the *dual* of $INDEPENDENT$ $SET$ $(IS)$, that is, we can find a vertex cover of size $k$ in a graph $G$ iff we can find an independent set of size $n-k$ in $G$. Play around with this a little and you'll see why this is true. If we then take the edge-complement graph $\bar{G}$ of $G$, an independent set of size $t$ in $G$ is the same as a clique of size $t$ in $\bar{G}$, so that gets us to $CLIQUE$.
> 2 votes

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


# Question
Title: $L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$
If $L$ is an APX-hard language, doesn't the existence of a PTAS for $L$ trivially imply $\mathsf{P} = \mathsf{NP}$?

Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT \[1\] unless $\mathsf{P} = \mathsf{NP}$. Thus if there was a PTAS for $L$ we could reduce metric-TSP using a PTAS reduction to $L$ and thus can approximate OPT within arbitrary precision.

Is my argument correct?

---

\[1\] Christos H. Papadimitriou and Santosh Vempala. On the approximability Of the traveling salesman problem. Combinatorica, 26(1):101–120, Feb. 2006.

# Answer
Some people (including more than one moderators) complained to me for posting an answer based on a comment, and I am tired of defending me from them. I asked them to delete this answer.
> 6 votes

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


# Question
Title: Find any of the 3 largest among $n$ elements
I have two questions. Both are about finding any of the 3 largest among $n$ elements.

1. How to show that $n-3$ comparisons **suffice** to find any of the $3$ largest among $n$ given numbers $(n \geq 4)$?
2. How to show that $n-3$ comparisons are **necessary** to find any of the $3$ largest among $n$ given numbers $(n \geq 6)$?

**My Idea**: I have tried to solve 1. using a heap but could not derive any such bound.

The place where I found this question gave one hint which said to analyze the number of connected components in a *comparison graph*.

I shall appreciate if anyone can throw some light on a *comparison graph*.

# Answer
> 9 votes
I don't know what do you mean by comparison graph. However, here is my solution for question 1.

Suppose you have a list of $m$ elements, and you want to find the largest element. You can do this with $m-1$ comparisons.

Do you know how to proceed?

> You can simply ignore the first two elements in your list. This gives you a new list $L'$ of $n'=n-2$ elements, You can determine the largest element of $L'$ with $n'-1=n-3$ comparisons. This element is one of the three largest.

---
Tags: algorithms
---


# Question
Title: Heuristics for an Artificial Intelligence problem
> **Problem** : Given a (one dimensional) row containing $2N$ tiles arranged in $2N + 1$ spaces. There are $N$ black tiles (B), $N$ white tiles (W), and a single empty space. The tiles are initially in an arbitrary ordering. Our goal is to arrange the tiles such that all white tiles are positioned to the left of the black ones, and one black tile is in the rightmost position. The goal position of the empty space is not specified.
> Tiles can be moved to the empty space when the empty space is at most $N$ cells away. Hence there are at most $2N$ legal moves from each state. The cost of each move is the distance between the tile and the empty space to which it moves ($1$ to $N$).

So I am doing this problem with A\* search algorithm with different heuristics(ofcourse admissible).So can anybody suggest me some heuristics.
Thanks

# Answer
All white tiles must be moved all the way to the left. Call the left most position 0. Then, in the final position, the sum of white distances from the axis is 0+1+...(N - 1).

Calculate this value, the "solution distance" of the tiles up front. As a heuristic, add the zero-based positions of white tiles up, and subtract from this sum the "solution distance" calculated a priori.

This heuristic gives you a minimal cost of finding a solution (eg. it will cost at least that much to get all white tiles in the correct place).
> 6 votes

---
Tags: artificial-intelligence, heuristics
---


# Question
Title: Graphs that cause DFS and BFS to process nodes in the exact same order
For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-shaped (trees of depth $1$ with an arbitrary number of children). Is there some way for categorizing graphs that satisfy this property?

# Answer
Assume our BFS and DFS have the rule to start from a specific node and both of them then visit the node with the lowest degree:

Start from left most black node, then both (BFS and DFS) traversals will visit left most red node, then they will visit next black node, and so on. To make it more general, you could add some paths in between triangles, or add star after finishing triangles.
> 6 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: What is the complexity of this subset merge algorithm?
**Updated Algorithm:** There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath.

---

The original algorithm posted had a major flaw in its working. I tried my best but could not get the desired accuracy in presenting the algorithm in pseudo code and/or Set Theory notation. I am thus posting python code, which has been tested and produces the desired results.

Note that my question, however, remains the same: What is the time complexity of the algorithm (assuming that powersets are already generated)?

```
# mps is a set of powersets; below is a sample (test case)
mps = [
        [       [], [1], [2], [1,2]     ],
        [       [], [3], [4], [3,4]     ],
        [       [], [5], [6], [5,6]     ]
      ]

# Core algorithm
# enumerate(mps) may not be required in languages like C which support indexed loops
len = mps.__len__()
for idx, ps in enumerate(mps):
    if idx > len - 2:
            break;
    mps[idx + 1] = merge(mps[idx], mps[idx+1])   # merge is defined below

# Takes two powersets and merges them
def merge (psa, psb):
    fs = []
    for a in psa:
            for b in psb:
                    fs.append(list(set(a) | set(b)))
    return fs

```

**Output**: `mps[-1] #Last item of the list`

Running the above example will result in listing out the powerset of $\\{1,2,3,4,5,6\\}$.

# Answer
> 3 votes
**EDIT:** Since your new algorithm is slightly different, I present a new complexity analysis. I change the notation slightly of power-sets $P\_a$ and $P\_b$ to $P\_1$ and $P\_2$. Your algorithm generates a power-set $P = P(S\_1 \cup S\_2 \cup \cdots \cup S\_n)$ where $P(S\_i)=P\_i$ given the power-sets $P\_1, P\_2, ..., P\_n$.
In the body of the loop it performs the merge of two subsets $P\_1$ and $P\_2$.

What is the complexity of $\mathtt{merge}(P\_1, P\_2)$?

Define $|a|=\mathtt{len}(a)$ for a list $a$. The complexity of $\mathtt{set}(a) \mid \mathtt{set}(b)$ is $\mathcal{O}(|a|+|b|)$ according to Python Wiki for the union of two sets. The conversion $\mathtt{list}(\mathtt{set}(a) \mid \mathtt{set}(b))$ is asymptotically not worse than $\mathcal{O}(|a|+|b|)$, I guess it is either linear or sublinear depending how python implements it. Appending is constant, but since you are appending the whole list it is linear in terms of one list element as the whole list object will need to be copied in the memory, again $\mathcal{O}(|a|+|b|)$ . Thus the complexity of the loop body in a merge function is at most $\mathcal{O}(3(|a|+|b|)$ which is asymptotically equivalent to $\mathcal{O}(|a|+|b|)$.

The loop body in a merge function will be executed $|P\_1||P\_2|$ times. Thus the overall complexity of the merge function is $\mathcal{O}(|P\_1||P\_2|(|a|+|b|))$. Notice $a$, $b$ are elements of power-sets. Thus their lengths follow a binomial distribution. Therefore on average $|a|=0.5\log\_2(|P\_1|)$ and $|b|=0.5\log\_2(|P\_2|)$. This gives us

\begin{align} \mathcal{O}(|P\_1||P\_2|(|a|+|b|))&=\mathcal{O}(|P\_1||P\_2|(0.5\log\_2(|P\_1|)+0.5\log\_2(|P\_2|))\\ &=\mathcal{O}(0.5|P\_1||P\_2|(\log\_2(|P\_1|)+\log\_2(|P\_2|))\\ &=\mathcal{O}(0.5|P\_1||P\_2|(\log\_2(|P\_1||P\_2|))\\ &=\mathcal{O}(|P\_1||P\_2|(\log\_2(|P\_1||P\_2|)) \end{align} for the complexity of a merge algorithm for two power-sets $P\_1$ and $P\_2$.

Notice that the merge of $P\_i$ and $P\_{i+1}$ replaces $P\_{i+1}$ for a power-set $\mathtt{merge}(P\_{i}$,$P\_{i+1})$ which is of length $2^{\log\_2|P\_i|+\log\_2|P\_{i+1}|}=|P\_i||P\_{i+1}|$.

After the first the first execution of the loop body in the main algorithm you will have executed $\mathcal{O}(|P\_1||P\_2|(\log\_2(|P\_1||P\_2|))$ steps. $P\_2$ has changed to $P\_2'$ with the length $|P\_1||P\_2|$. After the second execution you will get another $\mathcal{O}(|P\_2'||P\_3|\log\_2(|P\_2'||P\_3|))$ steps which is $\mathcal{O}(|P\_1||P\_2||P\_3|\log\_2(|P\_1||P\_2||P\_3|))$ And then by the induction you finally get the complexity of the last step of the loop \begin{align} \mathcal{O}(|P\_1||P\_2|\cdots|P\_n|\log\_2(|P\_1||P\_2|\cdots|P\_n|))&=\mathcal{O}(\Pi\_{i=1}^n|P\_i|\log\_2(\Pi\_{i=1}^n|P\_i|))\\ &=\mathcal{O}(\Pi\_{i=1}^n|P\_i|\Sigma\_{i=1}^n\log\_2|P\_i|). \end{align}

The complexity of the whole program is the sum of these complexities.

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


# Question
Title: Free variables of (λx.xy)x and bound variables of λxy.x
I was solving exercises on Lambda calculus. However, my solutions are different from the answers and I cannot see what is wrong.

1. Find free variables of $(\lambda x.xy)x$.
My workings: $FV((\lambda x.xy)x)=FV(\lambda x.xy) \cup FV(x)=\\{y\\} \cup \\{x\\}=\\{x,y\\}$.
The model answer: $FV((\lambda x.xy)x)=\\{x\\}$.
2. Find bound variables of $\lambda xy.x$.
My workings: A variable $y$ has its binding but since it is not present in the body of the $\lambda$-abstraction it cannot be bound and thus $BV(\lambda xy.x)=\\{x\\}$ only.
The model answer: $BV(\lambda xy.x)=\\{x, y\\}$.

# Answer
> 12 votes
1. Your answer is correct, $y$ is surely free. The model one is wrong. Maybe there was a typo and the answer was meant for $(\lambda y.xy)x$
2. It depends on the precise definition of $BV$. Often only $FV$ is defined formally, because it's more important. (Bound variables can be freely renamed in a subterm, but free variables can't.) So if $BV$ is defined as \begin{eqnarray\*} BV(x) &=& \\{\\} \\ BV(M N) &=& BV(M)\cup BV(N) \\ BV(\lambda x.M) &=& \\{x\\}\cup BV(M) \\ \end{eqnarray\*} then the model answer is correct. Note that this definition makes sense: If you have a term $M$ and substitute for a free variable $x$ another term $N$ with no bound variables ($BV(N)=\\{\\}$), you expect that $BV(M)=BV(M\[x:=N\])$. If you'd consider only bound variables that also appear under the $\lambda$, this property wouldn't hold.

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


title: What is a malformed token?

text:
# Question
Title: What is a malformed token?
I am reading Programming Language Pragmatics by Michael Scott. He says that on a first pass, a compiler will break a program into a series of tokens. He says that it will check for malformed tokens, like 123abc or $@foo (in C).

What is a malformed token? A variable that does not meet the rules of variable-naming? An operator that does not exist (ex. "\<-")?

Is this analogous to a misspelled word?

# Answer
The basic syntactic units in any *textual* programming language are tokens, which are, if you wish, the words in the programming language. The compiler parses these tokens to build sentences and so forth.

A malformed token is a string of characters that is not a valid word for the programming language.

It is not a variable that doesn't match the naming rules – not all tokens are variables. It is not an operator that is unknown – sometimes operators can be defined by the programmer. It is one of the smallest pieces of syntax that will never correspond to something sensible.
> 3 votes

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


# Question
Title: Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits
I was solving this equation: $$\text{key}=\left(\sum\_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$

### Given

$$ 1,000,000,000 \< a, n, m \\; \< 5,000,000,000, $$ $$ a, m \text{ are coprime}. $$

I solved it by brute force, but it won't work in the given constrains so I need a faster algorithm or is there is something I can notice to make the formula easier to solve ?

# Answer
Solve a linear homogeneous recurrence to obtain the identity $$\sum\_{K=0}^n\frac1{a^K}=\begin{cases}\frac{1-1/a^{n+1}}{1-1/a}&\text{if }a\neq1\pmod m\\n+1&\text{if }a=1\pmod m\end{cases}$$ and use efficient algorithms for multiplicative inversion and exponentiation mod $m$.
> 6 votes

---
Tags: algorithms, discrete-mathematics, number-theory
---


title: Produce decision version of the problem

text:
# Question
Title: Produce decision version of the problem
An optimisation problem requires minimising some function $f(x)$, where $x$ is a vector of integers. What is the corresponding decision version of the problem?

# Answer
> 4 votes
"Given $f(x)$, what is $\min(f(x))$?" becomes "Given $f(x)$, and $k$, decide if there is an $x$ such that $f(x)\< k$?"

---
Tags: complexity-theory, optimization, reductions
---


# Question
Title: Maximum Independent Subset of 2D Grid Subgraph
In the general case finding a Maximum Independent Subset of a Graph is NP-Hard.

However consider the following subset of graphs:

* Create an $N \times N$ grid of unit square cells.
* Build a graph $G$ by creating a vertex corresponding to every cell. Notice that there are $N^2$ vertices.
* Create an edge between two vertices if their cells share a side. Notice there are $2N(N-1)$ edges.

A Maximum Independent Subset of $G$ is obviously a checker pattern. A cell at the $R$th row and $C$th column is part of it if $R+C$ is odd.

Now we create a graph $G'$ by copying $G$ and removing some vertices and edges. (If you remove a vertex also remove all edges it ended of course. Also note you can remove an edge without removing one of the vertices it ends.)

By what algorithm can we find a Maximum Independent Subset of $G'$?

# Answer
As JeffE mentions in a comment, a grid graph is an example of a bipartite graph. If you take a bipartite graph, and remove some of the vertices, it will still be a bipartite graph.

Königs Theorem states, that for bipartite graphs, the number of vertices in a minimum covering, equals the number of edges in a maximum matching.

As mentioned in the answer for Maximum Independent Set of a Bipartite Graph:

> The complement of a maximum independent set is a minimum vertex cover

What you are asking, is how to find a maximum independent set in a grid graph with some vertices removed, and the way to do that, is to use some of the algorithms for finding a maximum matching in a bipartite graph, from that construct a minimum vertex cover, and then invert it to get a maximum independent set.

The figure below shows a bipartite graph with a maximum matching (in blue), a minimum vertex cover (in red) and consequently also a maximum independent set (in white):
> 9 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to compare the output of a neural network with his target?
I am coding a neural network implementation, but a I have problems in the design. I was wondering about how to compare the *output* with the *target*, my neural networks has three outputs

`groups = {'Iris-virginica':[0,0,1], 'Iris-setosa':[0,1,0], 'Iris-versicolor':[1,0,0]}`

I know I must translate each output to 0 and 1.

I meant if my result is `Iris-virginica` and my output is more or less: `[0.999979082561091, 0.9999918549147135, 0.9998408912106317]`, the subtraction would yield the following result:

`[-0.999979082561091, -0.9999918549147135, 0.000159]`

Is that correct, or I need to follow a different approach. Is possible train my net with 0, 1 and 2 values. Do I need to know any more?

# Answer
The easy answer: Take the predicted class to be the argmax of your output vector.

The longer answer: Since you're doing multiclass classification you should probably be using softmax output units (if I had to guess, I would guess you're using sigmoid output units). If $\mathbf{x} \in \mathbb{R}^n$ is the input to your output units then the softmax for the $i$th output unit is

$$ y\_i = \frac{\exp(x\_i)}{\sum\_{j}\exp(x\_j)} $$

This output function is nice for a number of reasons.

1. since your output vector sums to 1, you can interpret it probabilistically.
2. the derivative is particularly nice in combination with a log loss function.

Note: the further information I've provided may seen redundant since clearly

$$ \text{argmax}\\{\mathbf{x}\\} = \text{argmax}\\{\mathbf{\sigma(x)}\\} = \text{argmax}\\{\mathbf{\text{softmax}(x)}\\}, $$

where $\sigma$ is the elementwise logistic sigmoid function. The problem with just taking the argmax of what you have is you will likely not be optimizing the function you are actually interested in internally.

On the other hand the choice of loss function for classification isn't as cut and dry as I've made it sound.
> 2 votes

---
Tags: algorithms, neural-networks
---